Minimum-link paths among obstacles in the plane

ABSTRACT

Given a set of nonintersecting polygonal obstacles in the plane, the link distance between two points s and t is the minimum number of edges required to form a polygonal path connecting s to t that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in time &Ogr;(E&agr;(n) log2 n) (and space &Ogr;(E)), where n is the total number of edges of the obstacles, E is the size of the visibility graph, and &agr;(n) denotes the extremely slowly growing inverse of Ackermann's function.

REFERENCES

• 1: Pankaj Kumar Agarwal , Micha Sharir, Intersection and decomposition algorithms for arrangements of curves in the plane, 1989
• 2: J. Canny, J. Reif, New lower bound techniques for robot motion planning and real geometry, Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 1987, pp. 39-48.
• 3: B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Tech. Report UIUCDCS-R-1419, Department of Computer Science, University of Illinois at Urbana Champaign, March 1988.
• 4: H. Edelsbrunner , L. J. Guibas , J. Hershberger , R. Seidel , M. Sharir, Implicitly representing arrangements of lines or segments, Proceedings of the fourth annual symposium on Computational geometry, p.56-69, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73400]
• 5: H. Edelsbrunner , L. J. Guibas , M. Sharir, The complexity of many faces in arrangements of lines of segments, Proceedings of the fourth annual symposium on Computational geometry, p.44-55, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73399]
• 6: S.K. Ghosh and D.M. Mount, An output sensitive algorithm for computing visibility graphs, Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 1987, pp. 11-19.
• 7: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 8: S. Kapoor , S. N. Maheshwari, Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles, Proceedings of the fourth annual symposium on Computational geometry, p.172-182, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73411]
• 9: Y. Ke, An efficient algorithm for link-distance problems, Proceedings of the fifth annual symposium on Computational geometry, p.69-78, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73841]
• 10: J.S.B. Mitchell, An efficient algorithm for minimum link distance paths among obstacles in the plane, Manuscript, Cornell University, 1989.
• 11: J.S.B. Mitchell and E. Welzl, Dynamic methods for visibility graphs, Manuscript, Corneil University, 1989.
• 12: G. Rote and G. Woeginger, Computing a minimum link path among a set of obstacles in the plane, Manuscript, Technische Universit~t Graz, 1989.
• 13: S Suri , J O'Rourke, Worst-case optimal algorithms for constructing visibility polygons with holes, Proceedings of the second annual symposium on Computational geometry, p.14-23, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10517]
• 14: Subhash Suri, A linear time algorithm with minimum link paths inside a simple polygon, Computer Vision, Graphics, and Image Processing, v.35 n.1, p.99-110, July 1986 [doi>10.1016/0734-189X(86)90127-1]

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