Shortest paths in the plane with polygonal obstacles

ABSTRACT

We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required &OHgr;(n2 log n) time and O(n2) space, where n denotes the number of obstacle edges. Assuming that a triangulation or a Voronoi diagram for the obstacle space is provided with the input (if is not, either one can be precomputed in O(n log n) time), we present an O(kn) time algorithm, where k denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only O(n) space and, given a source point s, produces an O(n) size data structure such that the distance between s and any other point x in the plane (x) is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in O(1) time. The algorithm can also be used to compute shortest paths for the movement of a disk (so that optimal movement for arbitrary objects can be computed to the accuracy of enclosing them with the smallest possible disk).

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: Takao Asano , Tetsuo Asano , Leonidas Guibas , John Hershberger , Hiaroshi Imai, Visibility of disjoint polygons, Algorithmica, v.1 n.1, p.49-63, Jan. 1986 [doi>10.1007/BF01840436]
• 3: ~CHAZELLE, B. 1982. A theorem on polygon cutting with applications. In Proceedings oJ &e 23M ~1EEE Svmpostum on Foundations of Computer Science (Chicago, II1.). IEEE, New York, pp, ~339-349.
• 4: ~CHAZELLE, B. 1990. Triangulation of a simple polygon m linear time. In Proceedzngs of &e 31st ~Annum IEEE Svmpostum on Foundations of Computer Science. IEEE, New York, pp. 220 230,
• 5: L. Paul Chew, Planning the shortest path for a disc in O(n²log n) time, Proceedings of the first annual symposium on Computational geometry, p.214-220, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323261]
• 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: K. Clarkson , S. Kapoor , P. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)²) time, Proceedings of the third annual symposium on Computational geometry, p.251-257, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41985]
• 8: P. J. de Rezende , D. T. Lee , Y. F. Wu, Rectilinear shortest paths with rectangular barriers, Proceedings of the first annual symposium on Computational geometry, p.204-213, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323260]
• 9: ~DRYSDALE, R. L. 1979. Generahzed Voronoi diagrams and geometric searching. Tech. Rep. ~STAN-CS-79-705. Computcr Sci. Dept, Stanford Univ., Stanford, Calif.
• 10: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 11: ~FREI~ERICKSON, G. N 1984. Fast algorithms for shortest paths in planar graphs, w~th applica- ~tions. Teeh. Rep. CSD TR 486. Dcpt Comput. Scl, Purdue Univ., Lafayette, Ind.
• 12: ~FREDMAN, M. L., AND TARJAN, R. E. 1984. Fibonacci heaps and their uses in improved network ~optimization algorithms. In Proceedznb, s of the 25th Annual 1EEE Sympostum on the Foundattons ~oJ Computer Science (Singer Island, Fla.). IEEE, New York, pp. 338-346.
• 13: ~~:That is, a rounded obstacle space can be thought of as a regular obstacle space where some of ~the obtuse vertices have been replaced by arc segments.
• 14: L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
• 15: John Hershberger , Leonidas J. Guibas, An O(n2) shortest path algorithm for a non-rotating convex body, Journal of Algorithms, v.9 n.1, p.18-46, March 1988 [doi>10.1016/0196-6774(88)90003-X]
• 16: John E. Hopcroft , Deborah A. Joseph , Sue H. Whitesides, Movement Problems for 2-Dimensional Linkages, Cornell University, Ithaca, NY, 1982
• 17: Deborah A. Joseph , W. Harry Plantings, On the complexity of reachability and motion planning questions (extended abstract), Proceedings of the first annual symposium on Computational geometry, p.62-66, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323242]
• 18: ~KIRKPATRICK, D. G. 1979. Efficient computation of continuous skeletons. In Proceedings of the ~20th IEEE Symposium on Foundations of Computer Sctence. IEEE, New York, pp. 18-27.
• 19: KIRKPATRICK, D. G. 1983. Optimal search in planar subdivisions. SIAM J. Comput. }Z 1, 28-35.
• 20: ~LARSON, g. C., AND L1, V. O. K. 1981. Finding minimum rectilinear distance paths in the ~presence of barriers. Networks 11, 285-304.
• 21: ~LEE, D. t., AND PREPARATA, F. P. 1984. Euclidean shortest paths in the presence of rectilinear ~barriers. Networks 14, 393-410.
• 22: ~LIPTON, R. J., AND TARJAN, g. E. 1977. Applications of a planar separator theorem. In ~Proceedings of the iSth IEEE Symposium on Foundations of Computer Science. 1EEE, New York, ~pp. 162-170.
• 23: ~LOZANO-PEREZ, t. 1980. Automatic planning of manipulation transfer movements. Memo 606. ~Artificial Intelligence Laboratory, MIT, Cambridge, Mass.
• 24: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 25: ~MITCHELL, J. S. B. 1987. Shortest rectilinear paths among obstacles. Tech. Rep. 739. School of ~Operations Research and Industrial Engineering. Cornell Univ., Ithaca, N.Y.
• 26: ~MITCHELL, J. S. B., AND PAPADIMITRIOU, C. H. 1985. Planning shortest paths. SIAM Conference ~on Geometric Modeling and Robotics (Albany, N.Y.). SIAM, New York, pp. 1-21.
• 27: Joseph S. B. Mitchell , Christos H. Papadimitriou, The weighted region problem: finding shortest paths through a weighted planar subdivision, Journal of the ACM (JACM), v.38 n.1, p.18-73, Jan. 1991 [doi>10.1145/102782.102784]
• 28: Colm ó'Dúnlaing , Micha Sharir , Chee K. Yap, Retraction: A new approach to motion-planning, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.207-220, December 1983 [doi>10.1145/800061.808750]
• 29: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 30: ~REIF, J. H. 1979. Complexity of the mover's problem. In Proceedings of the 20th IEEE Sympo- ~sium on Foundations of Computer Science (San Juan, P.R.). IEEE, New York, pp. 421-427.
• 31: ~REIF, J. H., AND STORER, J. A. 1985. Shortest paths in Euclidean space with polyhedral ~obstacles. Tech. Rep. CS-85-121. Computer Sci. Dept., Brandeis Univ., Waltham, Mass.
• 32: ~SCHWARTZ, J. T., HOPCROFT, J. E., AND SHARIR, M. 1981. On the piano movers problem, l: The ~case of a 2-dimensional rigid polygonal body moving amidst barriers. Tech. Rep. TR39. ~Computer. Sci. Dept., New York Univ., New York, N.Y.
• 33: Jacob T. Schwartz , Micha Sharir , John E. Hopcroft, Planning, geometry, and complexity of robot motion, Ablex Publishing Corp., Norwood, NJ, 1986
• 34: ~SCHWARTZ, J. T., AND SHARIR, M. 1981. On the piano movers problem. 1: The case of ~2-dimensional rigid polygonal body moving amidst barriers. Tech. Rep. TR 39. Comput. Sci. ~Dept., New York Univ., New York.
• 35: ~SCHWARTZ, J. T., AND SHARIR, M. 1982. On the piano movers problem. 2: General techniques ~for computing topological properties of real algebraic manifolds. Tech. Rep. TR41. Comput. ~Sci. Dept., New York Univ., New York, N.Y.
• 36: ~SEDGEWICK, R., AND VITFER, J. S. 1984. Shortest paths in Euclidean graphs. In Proceedzngs of the ~25th Annual {EEE Symposium on the Theory of Computing (Singer Island, Fla.). IEEE, New ~York, pp. 417-424.
• 37: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 38: Michael Ian Shamos, Computational geometry., 1978
• 39: Micha Sharir( , Amir Schorr, On shortest paths in polyhedral spaces, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.144-153, December 1984 [doi>10.1145/800057.808676]
• 40: ~VACCARO, H. 1974. Alternative techniques for modeling distance. Masters Thesis m Civil ~Engineering. MIT, Cambridge, Mass.
• 41: ~WANGDAHL, a. E., POLLACK, S. M, AND WOODWARD, J B. 1974. Minimum-trajectory pipe ~routing. J. Ship Res. 18, 46-49.
• 42: ~WELZL, E. 19S5. Constructing the visibility graph for n-hne segments in O(n2) time. b~ Proc. ~Lett. 20. 167-171,
• 43: Ying-Fung Wu , Peter Widmayer , Martine D. F. Schlag , C. K. Wong, Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles, IEEE Transactions on Computers, v.36 n.3, p.321-331, March 1987 [doi>10.1109/TC.1987.1676904]
• 44: ~YAP, C K. 1984. An O(n log n) algorithm for the Voronoi diagram of a set of simple curve ~segments. Tech. Rep. Courant Inst. of Math. Sci., New York, New York, N Y.

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, Performance

Keywords:
Euclidean plane, minimal movement problem, motion planning, mover's problem, polygonal obstacles, robotics, shortest path