Delaunay Triangulation: Triangles With No Point Inside Their Circle

One rule: no point inside any circumcircle

Given a set of points in the plane, there are usually many ways to connect them into triangles that tile their convex hull. The Delaunay triangulation, named after the Russian-Soviet mathematician Boris Delaunay who described it in 1934, is the one specific triangulation with a remarkable property: for every triangle in it, the circle passing through its three vertices — its circumcircle — contains no other point of the set in its interior. Every triangle's circumcircle is empty.

That one rule has a powerful consequence: among all possible triangulations of a point set, the Delaunay triangulation is the one that maximises the minimum angle. It systematically avoids the long, thin sliver triangles that make finite-element meshes numerically unstable and terrain models look faceted and wrong. If a triangulation is not Delaunay, there exists a pair of adjacent triangles whose shared edge can be flipped to the other diagonal of their quadrilateral, and that flip always improves the worst angle — Delaunay is the state where no such improving flip exists.

Bowyer-Watson: insert a point, carve out a cavity

The algorithm you are watching above is Bowyer-Watson, published independently by Adrian Bowyer and David Watson in 1981. It builds the triangulation incrementally, one point at a time, and it works because the empty-circumcircle property is local and easy to test:

start with one huge "super-triangle" that encloses every input point

for each new point p:
    bad = every existing triangle whose circumcircle contains p
    cavity = the boundary polygon left after removing all "bad" triangles
    remove the bad triangles
    re-triangulate: connect p to every edge of the cavity boundary

remove any triangle still touching a super-triangle vertex

Testing whether a point lies inside a triangle's circumcircle is a single determinant sign test on the three vertices and the candidate point — cheap, exact with integer or careful floating-point arithmetic, and the reason incremental Delaunay code is short enough to fit on one screen. The super-triangle trick avoids having to special-case the convex hull boundary: everything starts inside one giant triangle, and the giant triangle's corners are stripped away at the end.

Bowyer-Watson is O(n log n) on typical point distributions when the search for bad triangles is accelerated with a spatial structure, but its worst case is O(n²): an adversarial insertion order can make a single new point invalidate a huge fraction of the mesh built so far. Fortune's sweepline algorithm and divide-and-conquer construction both guarantee O(n log n) in the worst case, at the cost of being considerably harder to implement correctly.

The Voronoi diagram is the same information, turned inside out

The Voronoi diagram partitions the plane into one cell per point, where a cell contains every location closer to that point than to any other. It looks like a completely different construction, but it is the exact dual graph of the Delaunay triangulation: connect the circumcenters of every pair of triangles that share a Delaunay edge, and you get the Voronoi edges. Every Delaunay triangle's circumcenter becomes a Voronoi vertex, and every Delaunay edge is crossed by exactly one perpendicular Voronoi edge. Compute one structure and the other is a linear-time traversal away.

Delaunay triangle          →  Voronoi vertex   (its circumcenter)
Delaunay edge (shared by
  two triangles)           →  Voronoi edge      (perpendicular, joining
                                                  the two circumcenters)
Delaunay vertex (a point)  →  Voronoi cell      (region closest to it)

Where this actually gets used

Finite-element meshers use Delaunay refinement to fill an engineering part with well-shaped triangles or tetrahedra because the empty-circumcircle property directly bounds the worst angle, which in turn bounds the numerical error of the simulation running on the mesh. Terrain and GIS software build a Delaunay triangulation over elevation samples (a TIN, triangulated irregular network) because it avoids the long thin triangles that make a landscape look artificially spiky. Wireless network planners use the Voronoi dual to model coverage cells around towers, and computational biologists use it to find each cell's nearest neighbours in a tissue. Both structures also answer nearest-neighbour queries directly: the Voronoi cell containing a query point identifies its nearest data point by construction, and the Delaunay triangulation is the sparsest graph guaranteed to contain the true nearest-neighbour edge for every point.

Frequently asked questions

Try it live

Everything above runs in your browser — open Delaunay & Voronoi and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.