a Delaunay triangulation
/ duh-loh-NAY /
Given a scatter of points in the plane, there are many ways to connect them into triangles. Most are ugly — full of thin slivers. The Delaunay triangulation is the canonical 'best' one: it connects the points into triangles that are as fat and well-shaped as possible, by a rule that sounds almost magical: no point of the set is allowed inside the circumscribed circle of any triangle. Empty circles everywhere.
Formally, for a set P of points in the plane (in general position, no four concyclic), the Delaunay triangulation DT(P) is the unique triangulation in which every triangle's circumcircle contains no point of P in its interior — the empty-circumcircle property. Equivalent characterizations: it maximizes the minimum angle over all triangulations of P (so it avoids slivers as much as possible), and it is the straight-line dual of the Voronoi diagram — two points are joined by a Delaunay edge exactly when their Voronoi cells share an edge. You can build it incrementally with edge flips (flip any edge that violates the empty-circle test, repeat until none remain), by a divide-and-conquer or sweepline algorithm in O(n log n), or by lifting the points onto a paraboloid in one higher dimension and taking the lower convex hull — the Delaunay triangulation is literally the projection of that hull, tying it to convex-hull algorithms.
Delaunay triangulations are foundational across computational geometry, meshing, and graphics: they give quality meshes for finite-element simulation, they are the natural connectivity for scattered-data interpolation and surface reconstruction, and on a surface the (intrinsic) Delaunay condition is exactly what guarantees nonnegative cotangent Laplacian weights, linking meshing quality to discrete differential geometry. Honest caveats: the maximize-minimum-angle optimality is special to two dimensions — in 3D, Delaunay tetrahedralizations can still contain slivers (nearly flat tetrahedra) despite the empty-sphere property, so 3D mesh quality needs extra work; and degeneracies (cocircular points) make the triangulation non-unique, requiring a tie-breaking rule or symbolic perturbation in robust code.
Take four points forming a thin, nearly-flat quadrilateral. Of the two ways to split it into two triangles, the Delaunay choice is the diagonal for which neither triangle's circumcircle contains the fourth point — the flip that makes the two triangles fattest. The edge-flip algorithm starts from any triangulation and repeatedly applies exactly this local test until every edge passes, converging to DT(P).
Of two possible diagonals, Delaunay picks the one with empty circumcircles — the fatter pair of triangles.
The max-min-angle optimality is a 2D phenomenon: Delaunay tetrahedralizations in 3D still admit slivers despite the empty-sphere property, so do not assume Delaunay means 'good mesh' in higher dimensions. Cocircular (degenerate) inputs make the triangulation non-unique and demand careful tie-breaking for robustness.