Voronoi Diagrams: Fortune's Sweep Line, Delaunay and Lloyd Relaxation

Definition and properties

Let P = {p₁, …, pₙ} be n distinct seed points in ℝ². The Voronoi cell of seed pᵢ is V(pᵢ) = {x ∈ ℝ² | d(x, pᵢ) ≤ d(x, pⱼ) for all j ≠ i}, using Euclidean distance by default (other metrics produce exotic variants). The boundaries between adjacent cells are bisectors — each edge is the perpendicular bisector of two seeds — and three cells meet at a Voronoi vertex, the circumcentre of the triangle formed by those three seeds. As the intersection of half-planes, every Voronoi cell is convex, and for a uniform Poisson point process the average cell has exactly 6 sides.

From brute force to Fortune's sweep line

The most direct approach is brute-force nearest-neighbour: for every pixel, scan all n seeds and colour it with the nearest one's colour — O(W·H·n), fine for small n but prohibitively slow at high resolution with thousands of seeds. Steven Fortune's 1987 algorithm computes the exact diagram in O(n log n) time by sweeping a horizontal line downward across the plane, maintaining an event queue (site events and circle events) and a beach line of parabolic arcs — each arc the locus of points equidistant from one seed and the sweep line. When a site event fires, the arc above the new seed splits and a new arc is inserted; when a circle event fires, three converging arcs collapse to a Voronoi vertex.

Algorithm              Time            Space   Notes
Brute force (raster)   O(W·H·n)        O(W·H)  Simple; GPU-parallel
Fortune's algorithm    O(n log n)      O(n)    Exact; reference implementation
Bowyer-Watson (dual)   O(n log n) avg  O(n)    Via Delaunay triangulation

Delaunay triangulation — the dual graph

The Delaunay triangulation DT(P) is the straight-line dual of the Voronoi diagram: connect two seeds whenever their cells share an edge. Its defining property is the empty-circumcircle criterion — no seed lies strictly inside the circumcircle of any triangle in DT(P) — which makes it maximise the minimum angle over all possible triangulations of the point set, exactly why it's the standard choice for finite-element meshes and numerical simulation grids where sliver triangles degrade accuracy. The Bowyer-Watson incremental algorithm builds it by inserting points one at a time, removing all triangles whose circumcircle contains the new point and re-triangulating the resulting hole.

Lloyd relaxation — centroidal Voronoi tessellation

A centroidal Voronoi tessellation (CVT) is a special Voronoi diagram where each seed coincides with the centroid of its own cell. Lloyd's algorithm iterates toward a CVT by alternating: compute the Voronoi diagram of the current seeds, then move each seed to the centroid — the weighted average position — of its cell. After 10-30 iterations the seeds distribute evenly, producing the characteristic foam-like, equal-area hexagonal pattern found in biological tissues, geographic districting and halftoning. Weighting each pixel by image darkness before relaxing produces Voronoi stippling, a dot-pattern technique popularised by Adrian Secord in 2002.

Applications in science, games and visualisation

Combined with the Delaunay graph, exact nearest-neighbour queries run in O(log n). Procedural terrain generators divide a plane into polygon "plates" or biomes via Voronoi + Lloyd relaxation, assigning height and moisture to each cell for instant believable geography. Biological cells — epithelial tissue, soap foam, honeycombs — all approximate Voronoi diagrams with the seed at the cell nucleus. In facility location, finding n warehouse locations that minimise average customer travel distance is exactly a centroidal Voronoi tessellation problem, and in real-time physics, fracture simulation uses Voronoi cells to define breakage shards by slicing a mesh along cell boundaries.

Frequently asked questions

Try it live

Everything above runs in your browser — open Voronoi Diagram and click to add sites, switch distance metrics, and watch Lloyd relaxation pull cells toward equal area in real time. Nothing is installed, nothing is uploaded.