There is a Planar Graph Almost as Good as the Complete Graph

Dartmouth Technical Report PCS-TR90-148

	L. Paul Chew

Date:  1990

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR90-148.pdf> (464KB)

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 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.