Approximating Shortest Paths on a Nonconvex Polyhedron
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (4), 1321-1340
- https://doi.org/10.1137/s0097539799352759
Abstract
We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in ${\mathbb R}^3$ and two points s and t on P, constructs a path on P between s and t whose length is at most ${7(1+{\varepsilon})} dP(s,t), where dP(s,t) is the length of the shortest path between s and t on P, and ${\varepsilon} 0$ is an arbitrarily small positive constant. The algorithm runs in O(n5/3 log5/3 n) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n8/5 log8/5 n) time and returns a path whose length is at most ${15(1+{\varepsilon})} d_{P}(s,t)$.
Keywords
This publication has 14 references indexed in Scilit:
- Constructing Approximate Shortest Path Maps in Three DimensionsSIAM Journal on Computing, 1999
- Practical methods for approximating shortest paths on a convex polytope in R3Computational Geometry, 1998
- 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
- Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsSIAM Journal on Computing, 1987
- Unobstructed Shortest Paths in Polyhedral EnvironmentsLecture Notes in Computer Science, 1987
- Toward Efficient Trajectory Planning: The Path-Velocity DecompositionThe International Journal of Robotics Research, 1986
- Voronoi diagrams with barriers and on polyhedra for minimal path planningThe Visual Computer, 1985
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979