the Delaunay triangulation
/ duh-loh-NAY /
Give a surveyor a scatter of measured points and ask them to connect the dots into triangles. There are many ways to do it, but most produce ugly slivers — long, thin, nearly-flat triangles that wreck calculations. The Delaunay triangulation is the one canonical way that avoids those slivers as much as possible: among all triangulations of a point set, it makes the triangles as 'fat' and well-proportioned as it can. It is the gold-standard mesh, and it is the geometric twin of the Voronoi diagram.
The defining rule is the empty-circle (or empty-circumcircle) condition, and it is checkable by hand. A triangulation of the points is Delaunay if, for every triangle in it, the circle passing through that triangle's three vertices (its circumcircle) contains NO other point of the set inside it. Equivalently and remarkably, the Delaunay triangulation is precisely the DUAL of the Voronoi diagram: connect two sites with an edge exactly when their Voronoi cells share a border, and the resulting network of triangles is the Delaunay triangulation. So the two structures carry the same information in complementary form — one tiles space by nearness, the other connects nearest neighbors — and either can be built from the other. Among its prized properties, the Delaunay triangulation maximizes the minimum angle over all triangulations, which is the precise sense in which it shuns thin slivers.
This makes it the default mesh-generator for finite-element simulation, terrain modeling from elevation samples, computer graphics, and interpolation of scattered data, and it can be computed in n log n time. Named for Boris Delaunay, a student of Voronoi, it inherits its elegance from that duality. Two honest cautions: first, the triangulation is unique only when no four points lie on a common circle — when they do (a 'degenerate' configuration like four corners of a square), there is a tie and more than one valid Delaunay triangulation exists. Second, although it maximizes the smallest angle, it does NOT minimize total edge length or guarantee every triangle is nice; it is the best by one specific, well-chosen criterion, not by all of them at once.
Four points forming a thin rectangle. You can split it into two triangles two ways: along one diagonal or the other. The Delaunay choice is the diagonal that keeps each triangle's circumcircle empty of the fourth point, which here is the SHORTER diagonal — it produces fatter triangles with a larger smallest angle, avoiding the sliver that the long diagonal would create. If instead the four points sat exactly on a circle (a square), both diagonals tie and either triangulation is Delaunay.
Pick the diagonal whose triangles have empty circumcircles; that is the Delaunay flip, and it fattens the triangles.
Delaunay maximizes the smallest angle, but that is its only optimality guarantee — it does not minimize total edge length, and when four points are concyclic the triangulation is not even unique.