A well shaped mesh
A triangulation connects a set of points into triangles that fill their convex hull. Many such triangulations exist, but the Delaunay triangulation is special: it avoids thin sliver triangles and is the dual of the Voronoi diagram.
The empty circle rule
The defining property is the empty circumcircle condition:
- For every triangle, draw the unique circle through its three corners.
- The triangulation is Delaunay if no other point lies strictly inside any such circle.
- Equivalently, it maximizes the smallest angle across all triangulations, which is why triangles look well proportioned.
This empty circle test is the local check that drives construction and verification.
Building and fixing
One simple construction inserts points one at a time and restores the property with edge flips: when an inserted point falls inside a neighbor triangle's circumcircle, you flip the shared edge to the other diagonal, repeating until every circle is empty again. Delaunay meshes underpin terrain modeling, finite element analysis, and interpolation, because their fat triangles give numerically stable results. Reading the diagram alongside its Voronoi dual makes both structures clearer.
Key idea
The Delaunay triangulation keeps every triangle's circumcircle empty of other points, which maximizes the smallest angle and avoids slivers.