The sweepline and incremental Delaunay triangulation implementations compared by Su and Drysdale [18] each use some variant of uniform bucketing to locate points. Bucketing yields fast implementations on uniform point sets, but is easily defeated; a small, dense cluster of points in a large, sparsely populated region may all fall into a single bucket. I have not used bucketing in Triangle, preferring algorithms that exhibit good performance with any distribution of input points. As a result, Triangle may be slower than necessary when triangulating uniformly distributed point sets, but will not exhibit asymptotically slower running times on difficult inputs.

Fortune's sweepline algorithm uses two nontrivial data structures in addition
to the triangulation: a priority queue to store events, and a
balanced tree data structure to store the sequence of
edges on the boundary of the mesh. Fortune's own implementation, available
from Netlib, uses bucketing to perform both these functions; hence,
an *O(n* log *n)* running time is not guaranteed, and
Su and Drysdale [18] found that the original implementation exhibits
*O(n ^{3/2})* performance on uniform random point sets.
By modifying Fortune's code to use a heap to store events, they
obtained

Triangle's implementation uses a heap as well, and also uses a splay
tree [17] to store mesh boundary edges, so that an
*O(n* log *n)* running time is attained, regardless of the
distribution of points. Not all boundary edges are stored in the splay tree;
when a new edge is created, it is inserted into the tree with probability
0.1. (The value 0.1 was chosen empirically to minimize the
triangulation time for uniform random point sets.) At any time, the
splay tree contains a random sample of roughly one tenth of the boundary edges.
When the sweepline sweeps past an input point, the point must be located
relative to the boundary edges; this point location involves a search
in the splay tree, followed by a search on the boundary of the triangulation
itself.

Splay trees adjust themselves so that frequently accessed items are near
the top of the tree. Hence, a point set organized so that many new vertices
appear at roughly the same location on the boundary of the mesh is likely
to be triangulated quickly. This effect partly explains why Triangle's
sweepline implementation
triangulates points on the boundary of a circle more quickly than the other
point sets, even though there are many more boundary edges in the cocircular
point set and the splay tree grows to be much larger
(containing *O(n)* boundary edges instead of *O(n ^{1/2})*).

Triangle's incremental insertion algorithm for Delaunay triangulation
uses the point location method proposed by
Mücke, Saias, and Zhu [14]. Their *jump-and-walk*
method chooses a random
sample of *O(n ^{1/3})* vertices from the mesh
(where

A more elaborate point location scheme such as that suggested by
Guibas, Knuth, and Sharir [9] could be used (along with
randomization of the insertion order) to obtain an
expected *O(n* log *n)* triangulation algorithm, but the
data structure used for location is likely to take up as much memory
as the triangulation itself, and unlikely to surpass the performance
of the divide-and-conquer algorithm; hence, I do not intend to pursue it.

Note that all discussion in this paper applies to Triangle version 1.2;
earlier versions lack the sweepline algorithm and many optimizations to
the other algorithms.

Mon Aug 12 10:28:49 EDT 1996