Constructing Approximate Shortest Path Maps in Three Dimensions
Author:
- Sariel Har-PeledSHSariel Har-Peled
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (4) , 1182-1197
Abstract
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.
Keywords
This publication has 22 references indexed in Scilit:
- Approximate Euclidean Shortest Paths in 3-SpaceInternational Journal of Computational Geometry & Applications, 1997
- Approximating shortest paths on a convex polytope in three dimensionsJournal of the ACM, 1997
- SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHSInternational Journal of Computational Geometry & Applications, 1996
- Triangulating a simple polygon in linear timeDiscrete & Computational Geometry, 1991
- Voronoi diagrams—a survey of a fundamental geometric data structureACM Computing Surveys, 1991
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- A sweepline algorithm for Voronoi diagramsAlgorithmica, 1987
- The Discrete Geodesic ProblemSIAM Journal on Computing, 1987
- Storing the subdivision of a polyhedral surfaceDiscrete & Computational Geometry, 1987
- A linear algorithm for determining the separation of convex polyhedraJournal of Algorithms, 1985