The Optimal Triangulation
Given a set of points, there are exponentially many ways to triangulate them. The Delaunay triangulation is special: it maximizes the minimum angle across all triangles, producing the 'fattest' possible mesh. This property, formalized by Boris Delaunay in 1934, makes it the gold standard for mesh generation in engineering simulation, terrain modeling, and computer graphics.
The Empty Circumcircle Property
Every Delaunay triangle has a circumscribed circle containing no other points. This elegant geometric invariant serves as both definition and algorithm: when inserting a new point violates the property, 'flip' the offending edge to restore it. The simulator highlights circumcircles in real time, letting you verify the property visually as points move.
Algorithms and Complexity
Three main algorithms construct Delaunay triangulations: incremental insertion (add points one by one, flipping edges), divide and conquer (split, triangulate halves, merge), and Fortune's sweep line (adapted from Voronoi computation). All achieve O(n log n) time — provably optimal since Delaunay triangulation can sort numbers.
From Meshes to Mountains
Delaunay triangulation powers countless applications. Finite element solvers need well-shaped meshes to avoid numerical instability — Delaunay guarantees this. Terrain models (TINs) use Delaunay triangulation of elevation points to create smooth, artifact-free surfaces. And in 3D reconstruction, Delaunay tetrahedralization extends the concept to volumetric meshing for medical imaging and structural analysis.