This section briefly overviews Delaunay Triangulation algorithms
for a given point set without constraining boundaries.
In two dimensions a naive edge swapping approach is less optimal, because
the number of required flip operations grows with
where
is
the number of points. Optimal algorithms run in
time and
depend on efficient data structures and point bucketing schemes.
For randomized point sets in two dimensions algorithms with expected linear
running time exist. In three dimensions the number of tetrahedra grows in the worst case
quadratically with the number of points. In practice for normal point
sets
algorithms are possible. It again depends on the
implementation of special data structures, search trees, and sorting.
A detailed comparison of Delaunay Triangulation algorithms can be found in
[174,47,15].
The following paragraphs provide sketches of the algorithms with simplified
explanations for the two-dimensional case. The three-dimensional versions
are analogous. The divide-and-conquer and the sweepline method have been
thoroughly tested in two dimensions. For a practical extension to three
dimensions the incremental methods seem most suitable.