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

Abstract

Given a polygonal domain $\cal 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 $\cal 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 $\cal 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 \cal P} \max_{p, q \in P_i} |pq|)$.