Two-point Approximate Shortest Path Queries among Convex Polygonal Obstacles in the Plane

Abstract

Given a polygonal domain $\mathcal{P}$ consisting $h$ pairwise disjoint convex polygonal obstacles together defined with $n$ vertices and a positive real number $\epsilon$ in $(0,0.6)$, this paper presents an algorithm to preprocess $\mathcal{P}$ in $O(n+\frac{h}{\epsilon }(h+\frac{1}{\sqrt{\epsilon }})\lg (\frac{h}{\sqrt{\epsilon }}))$ time to compute data structures of size $O(n+\frac{h}{\sqrt{\epsilon }}(h+\frac{1}{\epsilon }))$ so that given any two points $s$ and $t$ in the free space defined by $\mathcal{P}$, a path between $s$ and $t$ with a $(1+\epsilon )$ multiplicative stretch and $13\ell$ additive stretch is output in $O(\frac{1}{\sqrt{\epsilon }}(\lg \frac{h}{\sqrt{\epsilon }})+\frac{h}{{\epsilon }^{2.5}}(\lg \lg (\frac{h}{\sqrt{\epsilon }})))$ time. Here, $\ell$ is upper bounded by $(\sqrt{2\epsilon })({\max }_{P_i\in \mathcal{P}}{\max }_{p,q\in P_i}|pq|)$.