Delaunay Triangulation
Click to add points. The Delaunay triangulation maximizes the minimum angle of all triangles — no circumcircle of any triangle contains another point inside it. It is the dual graph of the Voronoi diagram.
Delaunay condition: the circumcircle of any triangle contains no other points | Bowyer-Watson incremental algorithm
Boris Delaunay (Delone) introduced this triangulation in 1934. The key property — no circumcircle contains a foreign point — maximizes the minimum angle, which is ideal for finite element meshes (avoiding poorly-conditioned "sliver" triangles).
The Bowyer-Watson algorithm adds one point at a time: find all triangles whose circumcircle contains the new point, remove them to form a polygon cavity, then re-triangulate the cavity with the new point. This runs in O(n log n) on average.
The Delaunay triangulation is the dual of the Voronoi diagram: connect the centers of neighboring circumcircles to get the Voronoi edges. Applications include terrain modeling, mesh generation, and nearest-neighbor graphs.