Delaunay triangulation

A Delaunay triangulation for a set of points in a plane is a triangulation such that no point lies inside the circumcircle of any triangle. This empty circumcircle property ensures that the triangles are as equiangular as possible, producing meshes that avoid sliver triangles and are well-suited for finite element analysis, interpolation, and surface reconstruction.

The Delaunay triangulation is the dual graph of the Voronoi diagram: two sites are connected by a Delaunay edge if and only if their Voronoi cells share a boundary. This duality means that algorithms for one structure often yield the other at negligible additional cost. The triangulation is unique when no four points are cocircular; degenerate configurations require tie-breaking rules that can subtly affect downstream computations.

The algorithmic history of Delaunay triangulation mirrors broader trends in computational geometry. Early divide-and-conquer algorithms achieved optimal O(n log n) time; later randomized incremental methods offered simpler implementations with the same expected bounds. In practice, the Bowyer-Watson algorithm — an incremental insertion method that locally retriangulates affected regions — dominates implementations because it handles dynamic updates and boundary constraints more naturally than static algorithms.