One dimension up, and the circles disappear

The Delaunay triangulation is defined by a condition nobody would choose. Join up a scatter of points into triangles so that no triangle’s circumcircle contains any other point — that is the definition, and every word of it is about circles, while the object being built is made of straight lines. Testing it means computing circumcircles. Proving anything about it means reasoning about which circles contain which points, and circles are not a convenient thing to reason about, because two of them can meet in a way that no linear algebra sees coming.

There is a trick that removes the circles entirely. It is one line long, it is exact rather than approximate, and it turns the whole subject into a statement about convexity.

The map #

Send the planar point $(x, y)$ to the spatial point $(x, y, x^2 + y^2)$. That is the whole construction. Every point of the plane goes vertically up onto a paraboloid, and the height it rises to is the square of its distance from the origin.

Nothing about that map mentions triangles, or circles, or nearness. It is a change of address, and it is not even a reversible one in any interesting sense — the third coordinate is a function of the first two, so no information is added and none is lost. Whatever is true of the lifted points was already true of the flat ones.

What changes is which statements are easy. The lifted points live in three dimensions, and in three dimensions the natural question to ask of a finite set of points is what its convex hull looks like. The hull of a set of points on an upward-curving surface has an underside and a top; the underside is what this rung is about.

Why the circles turn into planes #

The identity is short enough to write out, and it is worth writing out because everything else follows from it mechanically.

A circle in the plane, centred at $(a, b)$ with radius $r$, is the set of points satisfying

$$(x - a)^2 + (y - b)^2 = r^2,$$

which expands to

$$x^2 + y^2 - 2ax - 2by + (a^2 + b^2 - r^2) = 0.$$

Now read that as a statement about the lifted point. The first two terms are exactly the height $z$, and everything else is linear in $x$ and $y$. So the equation says

$$z = 2ax + 2by - (a^2 + b^2 - r^2),$$

which is the equation of a plane. The circle in the plane and the plane in space are the same equation, read at two addresses. And the inequality goes along with the equality: a point is inside the circle exactly when the left-hand side is negative, which is exactly when its lifted point sits below the plane.

That is the whole mechanism. Every circle in the plane is the shadow of a plane in space, and inside-the-circle is below-the-plane.

The same thing on a line, where every step is visible #

Two dimensions is one more than the picture needs. The identity is already there in one dimension, and in one dimension the whole argument fits on a single set of axes.

Take some points on a horizontal line and lift them to the parabola $y = x^2$. The circumcircle of two points on a line is the interval between them. The plane through two lifted points is the chord joining them. So the claim becomes: a third point lies between two others exactly when its lift is below their chord.

The algebra is a line. The chord through $(a, a^2)$ and $(b, b^2)$ has slope $a + b$, so its height at $x$ is $a^2 + (a+b)(x - a) = ax + bx - ab$. Subtract the parabola:

$$ax + bx - ab - x^2 = -(x - a)(x - b).$$

That product is positive precisely when $x$ is strictly between $a$ and $b$. The chord is above the parabola exactly along the interval and below it everywhere else, and there is no case analysis, no diagram-chasing, and nothing to check by hand. A geometric containment has become the sign of a quadratic.

Reading the picture twice with different pairs is the honest test of whether the identity is doing work or the figure is. The parabola has not moved and the points have not moved; only the chord has, and the verdict changes with it.

Two dimensions is the same statement with a plane in place of the chord and a paraboloid in place of the parabola, and the algebra is the same three lines. That is the sense in which the one-dimensional picture is not an analogy: it is the general argument with two of its variables set aside.

The condition, before and after #

The Delaunay condition in the plane reads: no triangle’s circumcircle contains another site. Every clause of that is now translatable.

Triangle becomes a triple of lifted points, which span a plane. Circumcircle becomes that plane. Contains another site becomes has another lifted point below it. So the condition reads: no triple’s plane has another lifted point below it — which is precisely the definition of a face of the lower convex hull.

So the two definitions are the same definition. One is stated in a language where the objects are circles and the natural algorithm is a search; the other is stated in a language where the object is a convex body and the natural algorithm is a hull. The second language has better tools in it, and that is the entire payoff.

Convexity is the property that makes local checks global. A convex hull can be certified by looking at each face and asking whether every point is on one side — a purely local test — and the certificate for the whole shape is the collection of certificates for its faces. Nothing about the circle formulation offers that. This is the same reason convexity makes an optimisation problem tractable: a local statement is allowed to be a global one.

The flip, which is the same fact told as a procedure #

Four points, and two ways to cut the quadrilateral they form into triangles. Exactly one of the two is Delaunay, unless the four happen to be concyclic, in which case both are and the choice does not matter.

In the lift, those two pictures are a pair of triangles that folds upwards and a pair that folds downwards. The illegal diagonal is a ridge; the legal one is a valley. Flipping the diagonal is pushing a ridge down into a valley, which lowers the surface, and that immediately gives the classical fact that repeated flipping terminates: each flip strictly lowers a finite piecewise-linear surface over a fixed set of points, and there are finitely many triangulations, so the process cannot cycle.

That termination argument is a good example of what the change of language buys. Stated in the plane it requires an ingenious potential function; stated in the lift the potential function is the height of the surface, which is not ingenious at all — it is the thing the picture is already made of.

Which way is up, and what the other side means #

Taking the faces whose plane has every other lifted point above it gives the Delaunay triangulation. Taking those with every point below gives something else, and it is not a curiosity.

By the same translation, a face of the upper hull is a triple whose circumcircle contains every other site. Its dual is the farthest-point Voronoi diagram: the division of the plane by which site is furthest away rather than nearest. And that diagram has a property the nearest-point one does not — an interior site has no cell at all, because no point of the plane has an interior site as its furthest.

The picture makes that obvious rather than surprising. A site strictly inside the convex hull of the others lifts to a point strictly inside the lower part of the lifted hull’s shadow, and such a point can be on the underside of the solid but never on its top. One solid, two sides, two diagrams, and the asymmetry between them is the asymmetry between the two sides of a convex body.

What it costs, and what it buys #

The cost is honest and small: computing a convex hull of $n$ points in three dimensions takes $O(n \log n)$ time, which is the same as the best planar Delaunay algorithms, and the constant is not obviously better. Nobody lifts to a paraboloid to gain a factor of two.

What is bought is everything else.

The first gain is that the theory becomes a special case rather than a subject. Convex hulls in three dimensions are studied for their own reasons; every theorem about them — Euler’s relation on the faces, the bound of $2n - 5$ on the number of facets, the behaviour under perturbation — descends immediately to statements about triangulations of points in the plane, and none of those has to be proved twice. The bound on the number of Delaunay triangles is the hull bound, and Euler’s relation is where it comes from.

The second is that degeneracies become visible instead of pathological. Four concyclic points in the plane are a nuisance: two triangulations tie and an algorithm has to choose. Lifted, they are four coplanar points, which is a perfectly ordinary thing for four points in space to be, and the standard treatment of coplanar hull faces handles them without a special case. The awkwardness did not go away; it was relocated to a place that already had machinery for it.

The third is that the construction generalises with no new ideas. Points in $d$ dimensions lift to $d+1$ dimensions and everything above still holds. The Delaunay triangulation of a set in three dimensions is the underside of a hull in four, and the fact that four-dimensional convexity is hard to picture does not stop it being easy to compute.

There is a fourth gain that belongs to the Voronoi diagram rather than to its dual, and it is the cleaner of the two statements. Take the tangent plane to the paraboloid at each lifted site rather than the site itself. Each such plane lies below the paraboloid everywhere except at its own point of tangency, so the upper envelope of the $n$ tangent planes is a convex piecewise-linear surface with one facet per site — and the facet belonging to site $i$ sits above exactly the points nearer to $i$ than to anything else. The Voronoi diagram is the shadow of that envelope.

So the two dual objects come from the two dual convex constructions: the diagram from an envelope of planes, the triangulation from a hull of points. The duality that was a combinatorial observation in the plane — cells share an edge exactly when sites are joined — is the standard duality between a convex body and its supporting planes. Nothing in the flat picture suggests that, and it is the reason the pair behaves as well as it does.

Where it fails, and the assumption doing the work #

The identity depends on the lifted surface being a paraboloid and on nothing else. Substitute a different surface and the correspondence breaks, because the expansion of the circle equation produced $x^2 + y^2$ exactly and would produce a mismatch for any other choice.

That means the trick is specific to the Euclidean notion of distance. The Voronoi diagram under a different metric — the taxicab or maximum metrics, whose unit circles are diamonds and squares — has bisectors that are not straight and cells that are not convex, and no lifting makes them into a hull. Any argument that proceeds by lifting is therefore an argument that has quietly assumed which distance is meant.

There is one substantial extension, and it is the subject of a later rung. Give each site a weight $w_i$ and lift it to height $x^2 + y^2 - w_i$ instead. The surface is no longer a single paraboloid — each point sits on its own translate of it — but the plane test is unaffected, because the weights are additive and the correspondence with circles becomes a correspondence with circles of shifted radius. That produces the power diagram, and the fact that it costs nothing is a hint that the weighted version is the natural one and the unweighted a special case.

Who noticed, and how late #

The two halves of this correspondence were established sixty years apart and by people working on unrelated questions, which is worth knowing because the modern presentation makes the connection look inevitable.

Voronoi’s diagrams and Delaunay’s triangulation came out of the theory of quadratic forms — Boris Delaunay’s 1934 paper is about which lattices are reduced, and the empty-sphere condition is a condition on a lattice basis rather than a proposal for a data structure. Convex hulls in three dimensions were, at the same time, a subject in polytope theory with no computational content at all, because there was nothing to compute with.

The lift is due to Kenneth Brown in 1979, in a paper written when both halves had become algorithmic and the question how expensive is a Voronoi diagram had started to matter. What he observed is the three-line expansion above. It had been available for a century.

That delay is the ordinary case rather than a scandal. The expansion is only interesting if somebody has a reason to want the lower hull of a point set, and until convex hulls were something one computed, “this condition is a hull condition” was not a useful thing to say. The identity was not hidden; it was uninteresting, and it stopped being uninteresting when the other half of it acquired algorithms.

The pattern recurs across this collection. A theorem’s exceptions are usually where its proof ran out, and a translation between two subjects is usually found when one of them acquires a tool the other wants — not when somebody notices the translation is possible.

What the picture cannot show #

The lifted solid is drawn with eight sites, and eight is a number chosen so the faces can be told apart. At forty sites the underside is a mesh of small triangles and the drawing communicates that a surface exists rather than which triangles it is made of. The claim is about arbitrary finite sets and the picture is about one small one.

The paraboloid is drawn as a coarse mesh, and it is not part of the object. The hull is determined by the lifted points alone; the surface is there to say where they came from. A reader could be forgiven for thinking the shaded faces are cut out of the paraboloid, and they are not — they are flat triangles strung between points that happen to lie on it, and the gap between a face and the surface above it is the thing the whole argument is about.

And the third dimension is drawn on a flat page, which is the standing difficulty with every projection: whether a face is genuinely below another is decided by the arithmetic, not by which of them looks nearer. The figure asserts the ordering rather than displaying it, and a reader who wants to check that a particular triangle is on the underside has to take the assertion’s word for it. The one-dimensional section exists partly for that reason — there, above and below are directions on the page.

Where the ladder goes next #

The lift settles what the triangulation is. The rungs above are about what happens when the sites are allowed to move, to carry weights, or to be treated as a graph rather than a diagram.

The next rung lets them move: each site walks to the centre of its own cell, repeatedly, and the diagram settles into something startlingly regular. The rung after gives them weights and watches the bisectors slide, which is the diagram that describes a foam. And the last of them reads the triangulation as a graph and finds a spanning tree already inside it, which is what makes several classical problems cheap.

Sideways, the move made here — solve a problem by embedding it in one dimension more and using a property the larger space has — is the same move as trading circles for lines by inversion, and the same move again as reading the plane as a sphere with one point added.

What is worth carrying away #

A definition that is hard to work with is often a definition stated in the wrong number of dimensions.

The empty-circumcircle condition is not wrong and not even inconvenient to state; it is simply written in a language whose objects — circles — have no useful ordering, no useful notion of local certification, and no useful algebra. Adding a coordinate that carries no new information converts every circle into a plane and every containment into an inequality, and inequalities are the thing mathematics is best at.

The habit worth taking is to notice when a condition is quadratic in disguise. The expansion of the circle equation has $x^2 + y^2$ sitting on its own, unattached to the parameters, and any condition of that shape is a linear condition on a lifted point. Once that is seen, the paraboloid is not a trick anybody had to invent — it is the only surface the algebra allows.