Approximate Euclidean shortest paths in polygonal domains

Abstract

Given a set $\mathcal{P}$ of $h$ pairwise disjoint simple polygonal obstacles in ${\mathbb{R}}^2$ defined with $n$ vertices, we compute a sketch $\Omega$ of $\mathcal{P}$ whose size is independent of $n$, depending only on $h$ and the input parameter $\epsilon$. We utilize $\Omega$ to compute a $(1+\epsilon )$-approximate geodesic shortest path between the two given points in $O(n+h((\lg n)+(\lg h{)}^{1+\delta }+(\frac{1}{\epsilon }\lg \frac{h}{\epsilon })))$ time. Here, $\epsilon$ is a user parameter, and $\delta$ is a small positive constant (resulting from the time for triangulating the free space of $\mathcal{P}$ using the algorithm in \cite{journals/ijcga/Bar-YehudaC94}). Moreover, we devise a $(2+\epsilon )$-approximation algorithm to answer two-point Euclidean distance queries for the case of convex polygonal obstacles.

a few updates; accepted to ISAAC 2019