The plane, divided by whoever is nearest

Put ten dots on a rectangle. For every other point of the rectangle, ask a single question — which dot is closest? — and shade it according to the answer.

The result is a tiling of the rectangle into ten regions, one per dot. Nobody chose the shapes, nobody drew the boundaries, and the boundaries are straight — which is the first thing worth explaining, because the rule that produced them says nothing about straightness.

Every boundary is a bisector #

Take two dots and ignore the rest. The points nearer to the first than to the second, the points nearer to the second, and the points exactly tied.

The tied points are exactly the perpendicular bisector of the segment joining the two dots, which is straight because being equidistant from two points is a linear condition in disguise: expand $|x - p|^2 = |x - q|^2$ and the quadratic terms cancel on both sides, leaving an equation of the first degree. That cancellation is the whole reason the diagram is made of line segments rather than curves.

It also settles the shape of a cell. A cell is the set of points nearer to its own site than to every other site, which is an intersection of half-planes — one per rival. An intersection of half-planes is convex, always, so every Voronoi cell is a convex polygon, however scattered the sites are and however many of them there are.

Two facts have now been established about a construction that mentions neither: the pieces are polygons, and they are convex. Both come from the algebra of the distance rather than from anything geometric, which is a good sign that the object is more natural than its definition looks.

The dual, and the property nobody put in #

Join two sites whenever their cells share an edge. That is a graph on the sites, and drawing it gives a triangulation of the region they occupy.

This is the Delaunay triangulation, and it has a property that ought to be startling: no triangle’s circumcircle contains any other site. Nothing in the construction mentioned a circle. The cells were built from distances, the edges from adjacency, and out comes a statement about circles through triples of points.

The reason is short once the right object is looked at. A Voronoi vertex — a corner where three cells meet — is equidistant from those three sites, because it is on all three bisectors at once. Equidistant from three points is precisely the definition of the circumcentre of the triangle they form. And it is a Voronoi vertex, so no fourth site is nearer to it than those three are, which is exactly the statement that the circumcircle is empty.

So the empty-circumcircle property is not an extra fact about the Delaunay triangulation. It is the Voronoi diagram’s defining property, read off the dual. The two structures are the same information, and which one is easier to think about depends entirely on the question.

That duality is the reason both objects are worth the trouble. It is the same kind of trade as colouring a map by turning it into a graph — one description throws away the shapes and keeps the adjacencies, and the discarded half is exactly what made the problem hard.

The circle test, which is the inscribed angle again #

Deciding whether a fourth point lies inside the circle through three others is the operation the whole construction turns on, and it connects straight back to a fact about angles.

Four points lie on a circle exactly when the quadrilateral they form has opposite angles summing to a straight angle, which is the cyclic-quadrilateral case of the inscribed angle theorem. Push the fourth point inside the circle and its angle grows past the complement; push it outside and the angle shrinks. So the in-circle test is an angle comparison wearing a determinant’s clothes, and the usual formulation of Delaunay — maximise the smallest angle over all triangulations — is the same criterion again.

That third formulation is the one that gets used in practice, and it is why Delaunay triangulations are the default for numerical work on scattered data. Long thin triangles ruin the conditioning of anything solved on them; the triangulation that avoids the smallest angles avoids the worst of that, and it happens to be the one the nearest-neighbour rule produces for free.

The equivalence of the three descriptions is worth a moment, because it is the kind of coincidence that usually is not one. A rule about distances, a rule about circles and a rule about angles pick out the same triangulation of the same points, every time. That happens when three descriptions are shadows of a single object seen from three sides, and here the object is a convex body one dimension up: lift each site vertically onto a paraboloid, take the lower half of the convex hull of the lifted points, and project it back down. The result is the Delaunay triangulation, and the empty-circumcircle condition becomes the entirely obvious statement that a face of a convex hull has nothing below it.

This is the same manoeuvre as seeing four conic sections as one cone cut four ways: several plane facts that look independent are one solid fact seen from underneath.

What it costs #

A naive construction is quadratic in the sites, or worse. Building each cell by cutting the plane with every rival’s bisector — which is what the figures here do, because ten sites make it free — costs $O(n)$ per cell and $O(n^2)$ overall, and the brute-force check that no circumcircle contains a site costs $O(n^4)$.

The real algorithms are $O(n \log n)$, which is optimal because a Voronoi diagram can sort. Fortune’s sweepline is the classical one: it passes a line across the plane and maintains the beach line, a chain of parabolic arcs separating the region where the diagram is already settled from the region a future site could still change. Parabolas appear because a point equidistant from a site and the sweepline traces one — the sweepline behaves like a directrix — so a construction with no conics in it produces conics as soon as it is computed rather than defined.

The complexity is also bounded in a way that is worth stating, because it is not obvious. A Voronoi diagram of $n$ sites in the plane has at most $2n - 5$ vertices and $3n - 6$ edges, which is linear rather than quadratic. The proof is Euler’s formula for planar graphs applied to the diagram: every Voronoi vertex has degree at least three, and counting incidences two ways bounds the faces. A structure that could in principle be dense is forced to be sparse by a topological identity, which is the sort of argument that makes a plane a nicer place to work than a space.

In three dimensions, and why the bound breaks #

The definition transfers unchanged: cells are intersections of half-spaces, so they are convex polyhedra, and the dual is a tetrahedralisation whose circumspheres are empty.

What does not transfer is the size. In three dimensions a Voronoi diagram of $n$ sites can have $\Theta(n^2)$ faces, and there are simple configurations that achieve it — two skew lines of points, each site on one line adjacent to every site on the other. The linear bound in the plane came from Euler’s formula, and Euler’s formula is a statement about surfaces rather than about solids, so it has nothing to say here.

That is a clean example of a dimension where intuition transfers and complexity does not, and it is the reason a great deal of computational geometry stops being practical at three. The picture is the same picture. The cost is squared.

Where it fails, and the assumption hiding in “nearest” #

Two conditions have been assumed silently.

The distance was Euclidean. Change the metric and the boundaries change with it. Under the taxicab metric — where distance is the sum of the coordinate differences, as on a grid of streets — the set of points equidistant from two sites is no longer a straight line: for sites on a diagonal it contains whole two-dimensional regions. Cells stop being convex polygons and can even fail to be connected. The construction survives; the theorems do not, and choosing a metric is a decision with consequences that reach much further than they look.

The sites were in general position. If four sites happen to lie on a circle, the Voronoi vertex where they meet has degree four rather than three, and the Delaunay dual is ambiguous — the quadrilateral can be split along either diagonal and both are legal. That is not a pathology to be swept aside. It is the case the in-circle predicate has to decide, in floating point, on points that are exactly balanced, and it is where implementations break.

The degenerate case is also where the two structures come apart. Voronoi is always well defined; Delaunay is not always unique. A duality that fails to be a bijection on a measure-zero set is still a duality, but the software has to pick.

Where it turns up, and why so often #

The construction is old and keeps being rediscovered, which is usually a sign that it is the right object rather than a clever one. Descartes drew something like it in 1644 for the distribution of matter in the solar system. Dirichlet used it in 1850 for quadratic forms and Voronoi in 1908 in the same setting. John Snow’s 1854 cholera map is the version everyone knows: the region of London nearer to the Broad Street pump than to any other pump, drawn to make an argument about where the disease came from.

The pattern is that any question of the form “which of these is closest” has this diagram as its answer, precomputed. Nearest-neighbour lookup becomes point location. Crystal growth from scattered seeds produces the diagram physically, because each seed’s grain is exactly the region it reaches first. The same is true of a great many territorial processes, which is why the cells turn up in the arrangement of cells in tissue, in the packing of seeds on a head, and in the cracking of mud — and it is why the same picture is the natural way to describe an arrangement grown outward from points.

What all of those share is that nothing in them is choosing a shape. The shapes are what is left over once every point has answered one question.

That last point deserves emphasis because it is the object’s one genuine awkwardness. A cell is not local. It is determined by the site’s neighbours, and which sites are neighbours is not known until the whole diagram has been built, so there is no way to compute one cell without effectively computing all of them. Adding a single site changes a bounded number of cells in practice and an unbounded number in the worst case, which is why incremental construction needs care and why the structure is rebuilt rather than patched in most applications.

Compare that with a triangulation of a polygon, where a cut is a local decision and the count of legal arrangements is what makes the object interesting. Here there is exactly one legal arrangement, and getting it needs global information.

What the picture cannot show #

The figures show ten sites. Everything interesting about the complexity — the linear bound in the plane, the quadratic blow-up in space, the $O(n \log n)$ algorithms — is invisible at ten, and a reader who takes the pictures as representative will have the wrong idea of the object’s cost. Ten sites is a picture of the definition, not of the problem.

The empty-circumcircle property is drawn for four triangles out of the twelve or so in the triangulation, because drawing all of them produces an unreadable tangle of overlapping circles. The generator checks every triangle against every site — that is the whole point of checking rather than illustrating — but the figure shows a sample, and a sample is not evidence.

And no figure here can show the failure under a different metric, because a picture of a taxicab bisector drawn on a Euclidean page looks like a Euclidean region and reads as a mistake.

The ladder from here #

Rungs above: Fortune’s sweepline drawn as it runs, with the beach line’s parabolas and the moment a site is swallowed. The lifting map, where projecting the sites onto a paraboloid turns the empty-circumcircle condition into a lower-convex-hull condition and the whole theory becomes three-dimensional convexity. Lloyd’s algorithm, which moves each site to its cell’s centroid and repeats, and the centroidal diagrams it converges to. Power diagrams, where the sites carry weights and the bisectors move — the version that describes soap froth. The medial axis, which is the Voronoi diagram of a shape’s boundary rather than of a set of points. And the relationship to the minimum spanning tree, which is always a subgraph of the Delaunay triangulation — the fact that makes the tree computable in $O(n \log n)$ instead of quadratically.

The construction is a question, not a shape #

It is worth ending on what makes this diagram different from the tilings elsewhere on this site.

A Reuleaux triangle is a shape someone designed to have a property. A regular solid is one of five things that exist. A Voronoi cell is neither: it is the answer to a question asked at every point of the plane at once, and its shape is a consequence with nobody’s intention behind it.

That is the reason the object recurs in so many unrelated settings. It is not that crystals and cholera pumps and seed heads have anything in common; it is that all three are situations in which something spreads from sources at a common rate, and “which source got here first” is the same question as “which source is nearest”. The diagram is what that question looks like when it is asked everywhere simultaneously, and the convex polygons, the straight boundaries and the empty circumcircles are all things that fall out afterwards.