BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR90-148
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: There is a Planar Graph Almost as Good as the Complete Graph
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Chew, L. Paul
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1990
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR90-148.pdf
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.
END:: ncstrl.dartmouthcs//TR90-148