Fast Greedy Triangulation Algorithms
Emo Welzl, Scot Drysdale, Matthew Dickerson
Institut für Informatik
Freie Universität Berlin
email: emo@inf.fu-berlin.de
Report B 94-09
April 94
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-09.ps.gz
The greedy triangulation of a set of $n$ points in the plane is the
triangulation obtained by starting with the empty set and repeatedly
adding the shortest compatible edge, where a compatible edge is defined
to be an edge that does not intersect any previously added edge. Computing
this triangulation efficiently is a classical problem in computational
geometry, and the triangulation is used in a number of applications.
This paper presents a practical algorithm that computes the greedy triangulation
of uniformly distributed points in expected time $O(n \log n)$ and a variant
that is less dependent on the uniform distribution. In the process
we give a method of testing the compatibility of an edge in $O(1)$ time
and show that almost all edges in a greedy triangulation are either
``short'' or have both endpoints ``near'' the convex hull of the triangulation.