BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR94-215
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Fast Greedy Triangulation Algorithms
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Dickerson, Matthew T.
AUTHOR:: Drysdale, Robert L. Scot
AUTHOR:: McElfresh, Scott A.
AUTHOR:: Welzl, Emo
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1994
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:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR94-215.ps.Z
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR94-215.pdf
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.
END:: ncstrl.dartmouthcs//TR94-215