Fast Greedy Triangulation Algorithms

Dartmouth Technical Report PCS-TR94-215

	Matthew T. Dickerson
	Robert L. Scot Drysdale
	Scott A. McElfresh
	Emo Welzl

Date:  1994

URL (compressed postscript): <http://www.cs.dartmouth.edu/reports/TR94-215.ps.Z> (104KB)

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR94-215.pdf> (280KB)

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.