Preprocessing-query tradeoffs in offline non-convex polygon separation queries

Abstract

This paper studies an offline translation-query problem between two simple polygons. Given polygons 𝐴 and 𝐵 and a query translation 𝑡 = (𝑑𝑥, 𝑑𝑦), the task is to compute an additional correction vector 𝑎 so that 𝐵 + 𝑡 + 𝑎 is separated from 𝐴, or reaches the minimum corrective translation required by the evaluated solver. Three methods are compared in a unified pipeline: Exact-NFP, Directional-Projection, and AABB-4Axis. Exact-NFP is used as the exact reference, DirectionalProjection is a directional approximation that preserves richer boundary information, and AABB-4Axis is a lightweight axis-aligned baseline. The complete main matrix contains 8 non-convex cases, covering vertex ranges 100-1000 and 1000- 2000, with 100000 intersecting queries per case. On this matrix, the average total time is 9994.048 ms for Exact-NFP, 37.271 ms for Directional-Projection, and 9.806 ms for AABB-4Axis. Directional-Projection reduces mean absolute error from 0.440092 to 0.317827 compared with AABB-4Axis, and reaches an 86.2340% hit rate under a 0.50 absolute-error tolerance. A separate 4000-5000 heavy-nonconvex stress case shows a sharper scalability gap: Exact-NFP requires 305340.731 ms, whereas Directional-Projection completes in 31.860 ms with a mean absolute error of 0.063676. These results indicate that Directional-Projection provides a favorable accuracy-speed tradeoff for offline non-convex polygon separation queries.