An optimal-time algorithm for shortest paths on a convex polytope in three dimensions

ABSTRACT

We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P in three dimensions. Our algorithm runs in O(nlog n) time and requires O(nlog n) space, where n is the number of edges of P. The algorithm is based on the O(nlog n) algorithm of Hershberger and Suri for shortest paths in the plane [11], and similarly follows the continuous Dijkstra paradigm, which propagates a "wavefront" from s along ∂P. This is effected by generalizing the concept of conforming subdivision of the free space used in [11], and adapting it for the case of a convex polytope in R³, allowing the algorithm to accomplish the propagation in discrete steps, between the "transparent" edges of the subdivision. The algorithm constructs a dynamic version of Mount's data structure [16] that implicitly encodes the shortest paths from s to all other points of the surface. This structure allows us to answer single-source shortest-path queries, where the length of the path, as well as its combinatorial type, can be reported in O(log n) time; the actual path π can be reported in additional O(k) time, where k is the number of polytope edges crossed by π.The algorithm generalizes to the case of m source points to yield an implicit representation of the geodesic Voronoi diagram of m sites on the surface of P, in time O((n+m)log(n+m)), so that the site closest to a query point can be reported in time O(log(n+m)).

REFERENCES

• 1: Pankaj K. Agarwal , Sariel Har-Peled , Micha Sharir , Kasturi R. Varadarajan, Approximating shortest paths on a convex polytope in three dimensions, Journal of the ACM (JACM), v.44 n.4, p.567-584, July 1997 [doi>10.1145/263867.263869]
• 2: L. Aleksandrov, A. Maheshwari, and J.-R. Sack, An improved approximation algorithm for computing geometric shortest paths, 14th FCT, Lecture Notes Comput. Sci. 2751:246--257, 2003.
• 3: Boris Aronov , Joseph O'Rourke, Nonoverlap of the star unfolding, Discrete & Computational Geometry, v.8 n.3, p.219-250, 1992
• 4: J. Chen and Y. Han, Shortest paths on a polyhedron, Part I: Computing shortest paths, Internat. J. Comput. Geom. Appl. 6:127--144, 1996.
• 5: J. Chen and Y. Han, Shortest paths on a polyhedron, Part II: Storing shortest paths, Tech. Rept. 161-90, Comput. Sci. Dept., Univ. Kentucky, Lexington, KY, February 1990.
• 6: James R. Driscoll , Daniel D. K. Sleator , Robert E. Tarjan, Fully persistent lists with catenation, Journal of the ACM (JACM), v.41 n.5, p.943-959, Sept. 1994 [doi>10.1145/185675.185791]
• 7: S. Har-Peled, Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions, Discrete Comput. Geom., 21:216--231, 1999.
• 8: Sariel Har-Peled, Constructing Approximate Shortest Path Maps in Three Dimensions, SIAM Journal on Computing, v.28 n.4, p.1182-1197, Aug. 1999 [doi>10.1137/S0097539797325223]
• 9: J. Hershberger and S. Suri, An optimal algorithm for Euclidean shortest paths in the plane, in Proc. 34th IEEE Sympos. Found. Comput. Sci., 508--517, 1993.
• 10: J. Hershberger and S. Suri, An optimal algorithm for Euclidean shortest paths in the plane, Manuscript, Washington University, 1995.
• 11: John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
• 12: Sanjiv Kapoor, Efficient computation of geodesic shortest paths, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.770-779, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301449]
• 13: Joseph S. B. Mitchell, Shortest paths and networks, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 14: Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
• 15: D. M. Mount, On finding shortest paths on convex polyhedra, Tech. Rept., Computer Sience Dept., Univ. Maryland, College Park, October 1984.
• 16: D. M. Mount, Storing the subdivision of a polyhedral surface, Discrete Comput. Geom., 2:153--174, 1987.
• 17: Joseph O'Rourke, Computational geometry column 35, ACM SIGACT News, v.30 n.2, June 1999 [doi>10.1145/568547.568559]
• 18: Joseph O'Rourke, Folding and Unfolding in Computational Geometry, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.258-266, December 09-12, 1998
• 19: J. O'Rourke, S. Suri, and H. Booth, Shortest path on polyhedral surfaces, Manuscript, The Johns Hopkins Univ., Baltimore, MD,1984.
• 20: Richard P. Paul, Robot Manipulators: Mathematics, Programming, and Control, MIT Press, Cambridge, MA, 1982
• 21: Y. Schreiber and M. Sharir, An optimal-time algorithm for shortest paths on a convex polytope in three dimensions, http://www.tau.ac.il/~syevgeny/ShortestPath.ps.
• 22: Micha Sharir, On shortest paths amidst convex polyhedra, SIAM Journal on Computing, v.16 n.3, p.561-572, June 1987 [doi>10.1137/0216038]
• 23: Micha Sharir , Amir Schorr, On shortest paths in polyhedral spaces, SIAM Journal on Computing, v.15 n.1, p.193-215, Feb. 1986 [doi>10.1137/0215014]
• 24: Kasturi R. Varadarajan , Pankaj K. Agarwal, Approximating Shortest Paths on a Nonconvex Polyhedron, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.182, October 19-22, 1997
• 25: E. W. Weisstein, Riemann Surface, MathWorld --- A Wolfram Web Resource, http://mathworld.wolfram.com/RiemannSurface.html.
• 26: E. W. Weisstein, Unfolding, MathWorld --- A Wolfram Web Resource, http://mathworld.wolfram.com/Unfolding.html.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations

General Terms:
Algorithms, Theory

Keywords:
continuous Dijkstra, geodesics, polytope surface, shortest path, shortest path map, unfolding, wavefront