Delaunay triangulation: from the Voronoi diagram

as the dual of the Voronoi diagram

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:

• 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 leaves an open figure, which is the inverse of the convex hull.  That is, the outermost edges of the triangles form the convex hull of the points.

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. 

This is the algorithm which is illustrated here.  We begin with the Voronoi diagram of the set of points, and from it construct the Delaunay triangulation.  The Voronoi diagram is computed by the intersecting half-plane algorithm (coming soon); then, an edge of the Voronoi diagram is removed and the corresponding Delaunay edge is inserted.  A Voronoi edge separates two points; the Delaunay edge connects them.

Movies

Four movies are provided:  for six, ten, and sixteen points.  An additional ten-point movie includes pauses at important steps when questions are posed to the viewer.

Remember the guidelines for the use of these movies.