Two-point Approximate Shortest Path Queries among Convex Polygonal Obstacles in the Plane
2026-08-10 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors developed a method to process a space containing several separate convex polygon obstacles so that later, they can quickly find a path between any two points in the free area. Their algorithm prepares data structures in a way that allows finding paths that are almost as short as the shortest possible path, up to a small factor and a limited additive error. The approach balances preprocessing time, storage size, and query speed, ensuring efficient pathfinding with guarantees on how close the path length is to the best possible. The results depend on how many obstacles exist and a parameter controlling the approximation accuracy.
polygonal domainconvex polygonpathfindingapproximation algorithmpreprocessingmultiplicative stretchadditive stretchcomputational geometrydata structureshortest path
Authors
Siddharth Gaur, R. Inkulu
Abstract
Given a polygonal domain $\cal P$ consisting $h$ pairwise disjoint convex polygonal obstacles together defined with $n$ vertices and a positive real number $ε$ in $(0, 0.6)$, this paper presents an algorithm to preprocess $\cal P$ in $O(n+\frac{h}ε(h+\frac{1}{\sqrtε})\lg(\frac{h}{\sqrtε}))$ time to compute data structures of size $O(n+\frac{h}{\sqrtε} (h+\frac{1}ε))$ so that given any two points $s$ and $t$ in the free space defined by $\cal P$, a path between $s$ and $t$ with a $(1+ε)$ multiplicative stretch and $13\ell$ additive stretch is output in $O(\frac{1}{\sqrtε}(\lg{\frac{h}{\sqrtε}})+\frac{h}{ε^{2.5}}(\lg{\lg(\frac{h}{\sqrtε})}))$ time. Here, $\ell$ is upper bounded by $(\sqrt{2ε}) (\max_{P_i \in \cal P} \max_{p, q \in P_i} |pq|)$.