5.3 Algorithms for Constructing a Delaunay Triangulation

This section briefly overviews Delaunay Triangulation algorithms for a given point set $P$ without constraining boundaries. In two dimensions a naive edge swapping approach is less optimal, because the number of required flip operations grows with $O(n^{2})$ where $n$ is the number of points. Optimal algorithms run in $O(n\log n)$ 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 $O(n\log n)$ 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.