Geometry in Action

Delaunay Triangulation

The Delaunay triangulation of a point set is a collection of edges satisfying an "empty circle" property: for each edge we can find a circle containing the edge's endpoints but not containing any other points. These diagrams their and their duals (Voronoi diagrams and medial axes)) have been reinvented, given different names, generalized, studied, and applied many times over in many different fields. The Delaunay triangulation is also closely related by the so-called "lifting transformation" to convex hulls in one higher dimension. Many common methods for function interpolation and mesh generation are based in some way on Delaunay triangulations, but there are also many other ways in which this structure has been applied.

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file.