Delaunay Triangulation
The Delaunay triangulation of a set of points in the plane divides the plane into a number of triangles, plus one open figure. The set of triangles is the "best" in the sense that:
The Delaunay triangulation is also the dual of the Voronoi diagram of these points. An edge of the triangulation maps to an edge of the diagram; a triangle maps to a Voronoi vertex; a vertex of the triangulation maps to a Voronoi cell.
- one couldn't add another triangle without going out of the plane
- the triangles maximize their smallest angle; that is, the triangles avoid being long and skinny.
The Delaunay triangulation is also the dual of the Voronoi diagram of these points. An edge of the triangulation maps to an edge of the diagram; a triangle maps to a Voronoi vertex; a vertex of the triangulation maps to a Voronoi cell.