%T There is a Planar Graph Almost as Good as the Complete Graph
%A L. Paul Chew
%R Technical Report PCS-TR90-148
%I Dartmouth College, Computer Science
%C Hanover, NH
%D  1990
%U http://www.cs.dartmouth.edu/reports/TR90-148.pdf
%X
 	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 that
 Ã10 times [ab], where [ab] is the straight-line Euclidean distance
 between a and b.  The triangulation that has this property is the L1
 metric Delauney triangulation for the set S.  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 O(n) size
 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.