Constructing Approximate Shortest Path Maps in Three Dimensions
Sariel Har-Peled · SIAM Journal on Computing · 1999
We present a new technique for constructing a data structure that approximates shortest path maps in $\Re^d$. By applying this technique, we get the following two results on approximate shortest path maps in $\Re^3$. (i) Given a polyhedral surface or a convex polytope $\P$ with n edges in $\Re^3$, a source point s on $\P$, and a real parameter $0 < \eps \leq 1$, we present an algorithm that computes a subdivision of $\P$ of size $O((n/\eps) \log( 1/\eps ))$ which can be used to answer efficiently approximate shortest path queries. Namely, given any point t on $\P$, one can compute, in $O(\log{(n/\eps)})$ time, a distance $\Delta_{\P,s}(t)$, such that $d_{\P,s}(t) \leq \Delta_{\P,s}(t) \leq (1 + \eps)d_{\P,s}(t)$, where $d_{\P,s}(t)$ is the length of a shortest path between s and t on $\P$. The map can be computed in $O(n^2 \log{n} + (n/\eps) \log{(1/\eps)} \log{(n/\eps)})$ time, for the case of a polyhedral surface, and in $O((n/\eps^3) \log ( 1/\eps ) + (n/\eps^{1.5}) \log{(1/\eps)} \log{n})$ time if $\P$ is a convex polytope. (ii) Given a set of polyhedral obstacles $\O$ with a total of n edges in $\Re^3$, a source point {\it s} in $\Re^3 {\rm \setminus \inter} \cup\scriptstyle{_{O \in \O}} O$, and a real parameter $0 < \eps \leq 1$, we present an algorithm that computes a subdivision of $\Re^3$, which can be used to answer efficiently approximate shortest path queries. That is, for any point $t \in \Re^3$, one can compute, in $O(\log{(n/\eps)})$ time, a distance $\Delta_{\O,s}(t)$ that $\eps$-approximates the length of a shortest path from {\it s} to {\it t} that avoids the interiors of the obstacles. This subdivision can be computed in roughly $O(n^4/\eps^6)$ time.