@TechReport{Dartmouth:TR90-148,
  author = {L. Paul Chew},
  title = {{There is a Planar Graph Almost as Good as the Complete Graph}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {PCS-TR90-148},
  year = {1990},
  URL = {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.
  }
}