Delaunay

Delaunay triangulation is a triangulation of a finite set of points in the plane, or of points in higher-dimensional space, in which the circumcircle of every triangle contains no other input point. It is named after the Russian-born French mathematician Boris A. Delaunay, who introduced the concept in 1934. In the plane it tends to avoid skinny triangles and maximizes the minimum angle of the triangles, producing more well-shaped elements for many point distributions.

One of its key properties is its dual relationship with the Voronoi diagram: the Delaunay triangulation is the geometric dual of the Voronoi tessellation of the same point set. Conversely, the Voronoi diagram’s edges are perpendicular bisectors of Delaunay triangle edges. The Delaunay triangulation generalizes to higher dimensions as the Delaunay tessellation, defined by the empty circumsphere condition for simplices.

Computing the Delaunay triangulation can be accomplished by several algorithms, including divide-and-conquer, incremental insertion with edge flips, and randomized methods. In two dimensions, the typical time complexity is O(n log n) for a set of n points. Robust implementations address degeneracies (co-circular points) and numerical precision with exact predicates.

Applications are widespread in computational geometry, computer graphics, geographic information systems, and engineering. Delaunay triangulations underpin mesh generation for finite element methods, interpolation schemes (such as natural neighbor interpolation), surface reconstruction, and spatial analysis. Variants include constrained Delaunay triangulations, which incorporate specified edges or boundaries.