There is a planar graph almost as good as the complete graph

ABSTRACT

Given a set S of points in the plane, there is a triangulation of S such that a path found within this triangulation has length bounded by a constant times the straight-line distance between the endpoints of the path. Specifically, for any two points a and b of S there is a path along edges of the triangulation with length less than √10 times |ab|, where |ab| is the straight-line Euclidean distance between a and b. Thus, a shortest path in this planar graph is less than about 3 times longer than the corresponding straight-line distance. The triangulation that has this property is the L1 metric Delaunay triangulation for the set 5. This result can be applied to motion planning in the plane. Given a source, a destination, and a set of polygonal obstacles of size n, an &Ogr;(n) size data structure can be used to find a reasonable approximation to the shortest path between the source and the destination in &Ogr;(n log n) time.

REFERENCES

• AAGHI85: T. ^sano, T. Asano, L. Guibas, J. Hershberger, H. Imal, Visibility-polygon search and Euclidean shortest paths, Proc. 26th IEEE Symposium on Foundations of Computer Science (1985), 155-164.
• CD85: L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
• Hw79: F. K. Hwang, An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees, Journal of the ACM (JACM), v.26 n.2, p.177-182, April 1979 [doi>10.1145/322123.322124]
• LS80: D.T. Lee and B. 5chachter, Two algorithms for constructing Delaunay triangulations, International Journal of Computer and Information Sciences, 9:3 (1980), 219-242.
• Pa85: C.H. Papadimitriou, An algorithm for shortest-path motion in three dimensions, information Processing Letters, 20 (1985), 259-263.
• SH75: M.I. $hamos and D. Hoey, Closest-point problems, Proc. 16th IEEE Symposium on Foundations of Computer Science (1975), 151-162.
• Sh85: M. Sharir, On shortest paths amidst convex polyhedra, Tech. Rept. 181, Computer $clence Division, Courant Institute of Mathematical Sciences (1985).
• SS84: 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]
• We85: E. Welzl, Constructing the visibility graph for n line segments in O(n2) time, Information Processing Letters, 20 (1985), 167-171.

INDEX TERMS

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Performance, Theory, Verification