Fast greedy triangulation algorithms

Abstract

The greedy triangulation (GT) 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 also be fast for many other distributions.