Approximate Euclidean shortest paths amid convex obstacles

ABSTRACT

We develop algorithms and data structures for the approximate Euclidean shortest path problem amid a set P of K convex obstacles in R² and R³, with a total of n faces. The running time of our algorithms is linear in n, and the size and query time of our data structure are independent of n. We follow a "core-set" based approach, i.e., we quickly compute a small sketch Q of P whose size is independent of n and then compute approximate shortest paths with respect to Q.

REFERENCES

• 1: Pankaj K. Agarwal , Boris Aronov , Subhash Suri, Stabbing triangulations by lines in 3D, Proceedings of the eleventh annual symposium on Computational geometry, p.267-276, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220308]
• 2: P. K. Agarwal, S. Har-Peled, and M. Karia. Computing approximate shortest paths on convex polytopes. In Algorithmica, 33:227--242, 2002.
• 3: 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]
• 4: L. Aleksandrov , A. Maheshwari , J.-R. Sack, Determining approximate shortest paths on weighted polyhedral surfaces, Journal of the ACM (JACM), v.52 n.1, p.25-53, January 2005 [doi>10.1145/1044731.1044733]
• 5: T. Asano, D. G. Kirkpatrick, and C. Yap. Pseudo approximation algorithms with applications to optimal motion planning. Discrete Comput. Geom., 31:139--171, 2004.
• 6: John Canny , John Reif, New lower bound techniques for robot motion planning problems, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, p.49-60, October 12-14, 1987 [doi>10.1109/SFCS.1987.42]
• 7: B. Chazelle and N. Shouraboura. Bounds on the size of tetrahedralizations. Discrete Comput. Geom., 14:429--444, 1995.
• 8: J. Chen and Y. Han. Shortest paths on a polyhedron, Part I: Computing shortest paths. Internat. J. Comput. Geom. Appl., 6:127--144, 1996.
• 9: J. Choi, J. Sellen, and C.-K. Yap. Approximate Euclidean shortest paths in 3-space. Internat. J. Comput. Geom. Appl., 7:271--295, 1997.
• 10: K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
• 11: K. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory, 10:227--236, 1974.
• 12: S. Har-Peled. Approximate shortest-path and geodesic diameter on convex polytopes in three dimensions. Discrete Comput. Geom., 21:216--231, 1999.
• 13: 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]
• 14: J. Hershberger and S. Suri. Practical methods for approximating shortest path on a convex polytope in R³. Comput. Geom. Theory Appl., 10:31--46, 1998.
• 15: 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]
• 16: Joseph S. B. Mitchell, Shortest paths and networks, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 17: Joseph S. B. Mitchell , Micha Sharir, New results on shortest paths in three dimensions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997839]
• 18: 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]
• 19: C. Papadimitriou. An algorithm for shortest path motion planning in three dimension. Inform. Process. Lett., 20:259--268, 1985.
• 20: A. Pogorelov. Extrinsic Geometry of Convex Surfaces, volume 35 of Transactions of Mathematical Monographs. American Mathematical Society, Providence, RI, 1973.
• 21: Franco P. Preparata , Roberto Tamassia, Efficient point location in a convex spatial cell-complex, SIAM Journal on Computing, v.21 n.2, p.267-280, April 1992 [doi>10.1137/0221020]
• 22: 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]
• 23: Yevgeny Schreiber , Micha Sharir, An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions, Discrete & Computational Geometry, v.39 n.1, p.500-579, March 2008 [doi>10.1007/s00454-007-9031-0]
• 24: 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]
• 25: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms