Delaunay tessellation (the Delaunay triangulation in the plane) is another fundamental computational geometry structure. The Delaunay tessellation is a “dual tessellation” of the Voronoi diagram. Here we will consider the planar Delaunay triangulation under the non-collinearity assumption.
 

Assumption 1     For a given set of points P = {p₁, p₂, …, p_n) subset Rm for all n ≤ 2, p₁, p₂, …, p_n are not on the same line [Delaunay 34].

 

In addition to this assumption we assume that the number of points in P is three or more but finite. Delaunay proved the following important theorem in 1934 that introduced the Delaunay triangulation.

Theorem 1    The straight-line dual of the Voronoi diagram for a set S belongs to E2 is a triangulation of S [Delaunay 34].

 

The Delaunay Triangulation (DT) is the straight-line dual of the Voronoi diagram obtained by joining all pairs of points p_i belongs to the set S whose Voronoi regions share a common Voronoi edge [Delaunay 34]. The Voronoi diagram and its dual Delaunay triangulation are shown below:

                                

Properties of Delaunay Triangulation

The Delaunay triangulation has been extensively studied in the literature and following is a list of important properties of the DT obtained under Assumption 1 (above).

Property    The external Delaunay edges in D(P) constitute the boundary of the convex hull of P.

Property    (Pitteway triangulation theorem)    The Delaunay Triangulation spanning P is a Pitteway triangulation spanning P if and only if every internal Delaunay edge crosses the associated Voronoi edge of the Voronoi diagram generated by P.

Property    All circumcircles of DT's are empty circles.

The empty circumcircles criterion: Given a triangulation of CH(P) spanning P, if the circumcircle of a triangle in the triangulation is an empty circle, we say that the triangle satisfies the empty circumcircle creterion.

With this criterion, we can show the following next property.

Property    Every triangle  in a triangulation spanning P satisfies the empty circumcircle criterion if and only if the triangulation is the Delaunay triangulation spanning P.

Incremental Methods

Here we distinguish between the incremental algorithm based on incremental construction and incremental algorithm based on incremental search.

1. The incremental construction algorithm adds points to the tessellation one by one, maintaining the Delaunay Triangulation [Guibas 92]. This method first locate the triangle containing the new point by applying counterclockwise test. Then it updates the tessellation by performing diagonal swaps on edges, based on the results of the INCIRCLE test.
2. The incremental search algorithm [Dwyer 91, L1 and Milenkovic 90] grow the  tessellation by adding one valid triangle at a time, starting with one Delaunay triangle and then performing a diagonal swap of an edge, if necessary, when a new triangle has to be considered. The worst-case complexity of algorithms based on incremental methods is θ(n²).

Reference

[1] L. Guibas, D. Knuth and M. Sharir, "Randomized incremental construction of Delaunay and Voronoi diagram", Algorithmica, 7(1992), p. 381-413.

Applet: