@TechReport{Dartmouth:TR94-215,
  author = {Matthew T. Dickerson and Robert L. Scot Drysdale and Scott A. McElfresh and Emo Welzl},
  title = {{Fast Greedy Triangulation Algorithms}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {PCS-TR94-215},
  year = {1994},
  URL = {http://www.cs.dartmouth.edu/reports/TR94-215.ps.Z},
  abstract = {
    The greedy triangulation of a set $S$ of $n$ points in the plane is
    the triangulation obtained by starting with the empty set and at each
    step adding the shortest compatible edge between two of the points,
    where a compatible edge is defined to be an edge that crosses none of
    the previously added edges.  In this paper we present a simple,
    practical algorithm that computes the greedy triangulation in expected
    time $O(n \log n)$ and space $O(n)$ for points uniformly distributed
    over any convex shape.  A variant of this algorithm should be fast for
    some other distributions.  As part of this algorithm we give an edge
    compatiblity test that requires $O(n)$ time for both tests and updates
    to the underlying data structure.  We also prove properties about the
    expected lengths of edges in greedy and Delaunay triangulations of
    uniformly distributed points.
  }
}