Approximating shortest paths on a convex polytope in three dimensions

ABSTRACT

Given a convex polytope P with n faces in R³ , points s,t∈6P , and a parameter 0<e≤1 , we present an algorithm that constructs a path on 6P from s to t whose length is at most 1+edP s,t , where dPs,t is the length of the shortest path between s and t on 6P . The algorithm runs in Onlog1/e+ 1/e³ time, and is relatively simple. The running time is On+1/e³ if we only want the approximate shortest path distance and not the path itself. We also present an extension of the algorithm that computes approximate shortest path distances from a given source point on 6P to all vertices of P.

REFERENCES

• 1: Avikam Balstan , Micha Sharir, On the shortest paths between two convex polyhedra, Journal of the ACM (JACM), v.35 n.2, p.267-287, April 1988 [doi>10.1145/42282.214094]
• 2: CANNY, J., AND REIF, J. H. 1987. New lower bound techniques for robot motion planning problems. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 49-60.
• 3: CHAZELLE, B., EDELSBRuNNER, n., GUIBAS, L., AND SHARIR, M. 1993. Diameter, width, closest line pair, and parametric searching, Disc. Comput. Geom. 10, 183-196.
• 4: Jindong Chen , Yijie Han, Shortest paths on a polyhedron, Proceedings of the sixth annual symposium on Computational geometry, p.360-369, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98601]
• 5: Joonsoo Choi , Jürgen Sellen , Chee-Keng Yap, Approximate Euclidean shortest path in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.41-48, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177501]
• 6: K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
• 7: DOBKIN, D., AND KIRKPATRICK, D. 1985. A linear algorithm for determining the separtaion of convex polyhedra, J. Algorithms 6, 381-392.
• 8: David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
• 9: DUDLEY, R. M. 1974. Metric entropy of some classes of sets with differentiable boundaries, J. Approx. Theory 10, 227-236.
• 10: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 11: Sariel Har-Peled, Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions, Proceedings of the thirteenth annual symposium on Computational geometry, p.359-365, June 04-06, 1997, Nice, France [doi>10.1145/262839.263003]
• 12: HAR-PELED, S. 1997. Constructing approximate shortest path maps in three dimensions. Manuscript.
• 13: John Hershberger , Subhash Suri, Practical methods for approximating shortest paths on a convex polytope in R3, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.447-456, January 22-24, 1995, San Francisco, California, United States
• 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: PAPADIMITRIOU, C. H. 1985. An algorithm for shortest-path motion in three dimensions, Inf. Process. Lett. 20 259-263.
• 16: POGORELOV, A. V. 1973. Extrinsic Geometry of Convex Surfaces. Volume 35 of Translations of Mathematical Monographs. American Mathematical Society, Providence, R.I.
• 17: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 18: John H. Reif , James A. Storer, A single-exponential upper bound for finding shortest paths in three dimensions, Journal of the ACM (JACM), v.41 n.5, p.1013-1019, Sept. 1994 [doi>10.1145/185675.185811]
• 19: 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]
• 20: 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]
• 21: 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

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

General Terms:
Algorithms, Theory

Keywords:
Euclidean shortest paths, approximation algorithms, convex polytopes