There Is a Planar Graph Almost as 600d as the Complete Graph

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 stralght-Iine 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 410 times labl, where labl 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 L 1 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 slze n, an O(n) slze data structure can be used to find a reasonable approximation to the shortest path between the source and the destination in O(n log n) time. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is b