Fast Greedy Triangulation Algorithms

Emo Welzl, Scot Drysdale, Matthew Dickerson Institut für Informatik Freie Universität Berlin email: Report B 94-09 April 94

Get the report here or by anonymous ftp: 
File:   pub/reports/
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.