Delaunay Triangulation

A Delaunay Triangulation of a set of points in a plane is a triangulation with the property that every edge is contained in a circle that contains no other points of the set. This implies that the circumcircle, or outcircle, of each triangle contains no other points from the set. The Delaunay Triangulation guarantees that the smallest angle will be maximal.

It's also the AdjacencyGraph of the VoronoiDiagram, and this definition generalises to higher dimensions in an obvious way.

One would hope that the Delaunay Triangulation would be the result of repeatedly joining the two closest points unless doing so would cross an edge you already have, but sadly that turns out not to be the case. Take a kite with its head angle close to 180 degrees and its tail angle quite small. The two closest points are the side points, but the DelaunayTriangulation joins the head to the tail.

CategoryMath