Shortest paths on a polyhedron

ABSTRACT

We present an algorithm for determining the shortest path between a source point and any destination point along the surface of a polyhedron (need not be convex). Our algorithm uses a new approach which deviates from the conventional “continuous Dijkstra” technique. It takes &Ogr;(n2) time and ⊖(n) space to determine the shortest path and to compute the inward layout which can be used to construct a structure for processing queries of shortest path from the source point to any destination point.

REFERENCES

• AAOS: P. Agarwal, B. Aronov, J. O'Rourke, and C. Schevon, Star unfolding of a polytope with applications (extented abstract} Tee. Rep. 90.2.13, February 1990.
• Ca: J. Canny, A New algebraic method for robot motion Planning and Real Geometry, Proe. 1987 IEEE FOCS, 39-48.
• CH: J. Chen and Y. Han, Shortest paths on a polyhedron, Part 1I: storing shortest paths, TR No. 161-90, Computer Sci. Dept., University of Kentucky, Lexington, Kentucky, February, 1990.
• CR: J. Canny, J. Reif, New lower bound techniques for robot motion planning problems, Proe. i987, IEEE FOCS, 49-60.
• Di: E. W. Dijkstra, A note on two problems in connection with graphs, Numer. Math., 1(1959), pp. 269-271.
• GJPT: M. R. Garey, D. S. Johnson, F. P. Preparata and R. E. Tarjan, Triangulating a simple polygon, Inform. Process. Lett., 7(1978), pp. 175-179.
• HCT: Yie-Huei Hwang , Ruei-Chuan Chang , Hung-Yi Tu, Finding All Shortest Path Edge Sequences on a Convex Polyhedron, Proceedings of the Workshop on Algorithms and Data Structures, p.251-266, August 17-19, 1989
• Ki: D. G. Kirkpatrick, Optimal search in planar subdivisions, SIAM J. COMPUT. 12(1983), pp.28-35.
• Mi1: J. S. B. Mitchell, Shortest paths in the plane in the presence of obstacles, Manuscript, Dept. of Operations Research, Stanford Univ., Stanford, CA, 1984.
• Mi2: J. S. B. Mitchell, Planning shortest paths, Ph.D. thesis, Dept. of Operation Research, Stanford, CA, August, 1986.
• MMP: 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]
• Mol: D. M. Mount, On finding shortest paths on conve~ polyhedra, Technical Report 1495, Department of Computer Science, University of Maryland, Baltimore, MD, 1985.
• Mo2: D. M. Mount, The number of shortest paths on the surface of a polyhedron, Tee. Rep., Computer Sci. Dept., Univ. of Maryland, College Park, 1986.
• OSB: J. O'Rourke, S. Suri and H. Booth, Shortest path on polyhedral surfaces, Manuscript, The Johns Hopkins Univ., Baltimore, MD, 1984.
• Pr: F. P. Preparata, New approach to planar point location, SIAM J. COMPUT. 10(1981), pp.473-482.
• RS1: J. Reif, J. A. Storer, Shortest paths in Euclidean space with polyhedral obstacles, Tee. Rep. CS-85-121, Computer Science Dept., Brandeis Univ., Waltham, MA, April, 1985.
• RS2: John H. Reif , James A. Storer, 3-Dimensional Shortest Paths in the Presence of Polyhedral Obstacles, Proceedings of the Mathematical Foundations of Computer Science 1988, p.85-92, August 29-September 02, 1988
• SH: M. Shamos and D. Hoey, Closest-point problems, Proc. 17th Annual IEEE FOCS, (Oct. 1975) pp. 151- 162.
• SO: C. Schevon, J. O'Rourke, The number of maximum edges sequences on a convex polytope, Proe. Allerton Conference, 1988.
• SS: 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:
  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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms