When the sites are not the same size

The nearest-neighbour diagram treats every site alike. That is a strong assumption dressed as no assumption at all, and it is wrong about almost every situation the diagram gets used for. Shops are not the same size, transmitters are not the same power, atoms are not the same radius, and bubbles in a foam are not the same pressure. In each case the boundary between two territories should sit somewhere other than halfway.

The natural repair is to give each site a weight and let the boundary move. What is not natural, and is the reason this rung exists, is that there is a right way to do that — one which keeps every cell convex, keeps every boundary straight, and keeps the entire theory of the previous rungs intact — and every other way is worse in ways that are easy to miss.

Comparing the two pictures is the fastest way to see what a weight does and what it does not. The boundaries have not bent, tilted or curved: each one has slid along the line joining its own pair, and nothing else about the diagram has changed shape. That invariance is not obvious in advance and is the whole content of the next two sections.

The wrong repairs, first #

Two obvious weightings are worth ruling out before the right one arrives, because each is used in practice and each breaks something.

Multiplying the distance — assign the point $x$ to the site minimising $|x - s_i| / w_i$ — gives the multiplicatively weighted diagram, sometimes called the Apollonius diagram after the circles his problem produces. The set of points equidistant in that sense from two sites is a circle, not a line, which is a classical fact going back to the same source. So the cells are bounded by circular arcs, they need not be convex, and a single cell can be disconnected. Everything from the previous rungs stops applying.

Subtracting the distance — minimise $|x - s_i| - w_i$ — gives the additively weighted diagram, whose bisectors are branches of hyperbolas. Better than circles, still not lines, still not convex.

Subtracting the weight from the squared distance — minimise $|x - s_i|^2 - w_i$ — gives straight bisectors, and it is the only one of the three that does. The reason is one line of algebra, and it is the same line as the last rung’s.

The one line #

The boundary between sites $i$ and $j$ is where the two quantities agree:

$$|x - s_i|^2 - w_i = |x - s_j|^2 - w_j.$$

Expand both sides. Each contains $|x|^2$, and those cancel — the whole of the quadratic part disappears, leaving

$$2(s_j - s_i) \cdot x = |s_j|^2 - w_j - |s_i|^2 + w_i,$$

which is the equation of a line perpendicular to $s_i s_j$, exactly like the unweighted bisector, but displaced along that direction by an amount depending on the difference of the weights. Set the weights equal and the displacement is zero and the line is the perpendicular bisector.

So a cell is again an intersection of half-planes, and therefore again convex; the diagram again tiles the plane with polygons; and every argument from the previous rungs that used only convexity survives untouched. The construction is called the power diagram, and the quantity $|x - s_i|^2 - w_i$ is the power of the point $x$ with respect to the circle of radius $\sqrt{w_i}$ centred at $s_i$.

Reading that figure against the hero is the argument for the last paragraph. A boundary’s direction is fixed by the two sites and nothing else; a boundary’s position is the only thing a weight can touch. Any weighting scheme that rotates or curves a boundary is doing something to the geometry rather than to the balance between two sites, which is why the two rejected repairs above are rejected.

What the power actually measures #

The word is not decoration. Draw the circle of radius $\sqrt{w_i}$ about $s_i$. For a point $x$ outside it, the power $|x - s_i|^2 - w_i$ is exactly the square of the length of the tangent from $x$ to that circle — by Pythagoras on the triangle made of the centre, the point, and the point of tangency, where the tangent meets the radius at a right angle.

That reading makes the diagram intelligible. A point belongs to the site whose circle it can touch with the shortest tangent. Inside a circle the power is negative and there is no tangent, which is the case that produces the interesting behaviour below.

It also explains the boundary. The locus of equal power to two circles is the classical radical axis, and when the circles cross, the radical axis is the line through the two crossing points — because a crossing point is on both circles, so its power to each is zero. That is a check with real content, since it fixes the boundary’s position by a property of the circles rather than by the formula that drew it, and the hero figure verifies it at every crossing pair.

The tangent reading also settles a question the formula leaves open: what happens inside a circle, where there is no tangent to measure. The power is negative there, and the smaller it is the more strongly the site claims the point — so a large circle claims its own interior emphatically, which is exactly the behaviour wanted of a large shop, a strong transmitter or a big atom. The formula and the picture agree about the sign, and the picture is the one that explains why the sign is right.

The cell that is not there #

In the unweighted diagram, every site owns at least the ground it stands on: the distance from a site to itself is zero and to everything else is positive, so a small region around each site is always its own. That is not a deep fact; it is an immediate consequence of distance being non-negative.

Power is not non-negative. A site sitting inside a much larger neighbour’s circle has positive power to itself and negative power to the neighbour, so it loses at its own position — and often loses everywhere.

The arithmetic is worth doing once, because the threshold has a clean form. Site $i$ beats site $j$ at its own position exactly when $-w_i < d^2 - w_j$, where $d$ is the distance between them, which rearranges to $w_j - w_i < d^2$. So a site survives at its own location precisely when no neighbour’s weight exceeds its own by more than the squared distance to it — and in circle language that says the neighbour’s circle does not swallow it. Losing at one’s own position does not yet prove losing everywhere, but in practice the two go together, and the threshold in the figure below is found by search rather than by that formula for exactly that reason.

This is a genuine break with the earlier rungs and not a technicality. A power diagram of $n$ sites may have fewer than $n$ cells, so the map from sites to cells is not a bijection, and any algorithm or argument assuming it is will be wrong on exactly the inputs where the weights are doing something.

It is also the feature that makes the construction useful. A site with no cell is a site whose influence is entirely accounted for by its neighbours, and in the applications that is meaningful information rather than a degenerate case: an atom buried inside larger ones contributes no surface, a transmitter drowned by its neighbours reaches nobody.

The lift, again, with the weights in it #

The last rung showed that the Delaunay triangulation is the lower convex hull of the sites lifted to the paraboloid $z = |s|^2$. Weights change that construction by a single term, and the term is the one convexity does not notice.

Lift site $i$ to the height $|s_i|^2 - w_i$. The plane test is unaffected — a weight is a constant subtracted from one height, and a plane through three lifted points is still determined by three linear equations — so the whole correspondence goes through unchanged, and what comes out is the regular triangulation, the dual of the power diagram.

And the vanishing cells become obvious. In the unweighted case every lifted point is on the paraboloid, and every point of a strictly convex surface is a vertex of its own convex hull — that is what strict convexity means. Once the heights are lowered by different amounts the points are no longer on any convex surface, so some of them can sit strictly inside the hull, and a lifted point inside the hull is a site with no cell.

That is the cleanest statement of the whole rung. Weights do not add a new construction; they remove the accident that every point was extreme. The unweighted diagram is the special case in which nothing can be buried, and it is special for a reason with nothing to do with distance.

That figure is worth staring at for a moment. Stripped of its circles the picture is an ordinary convex tiling with straight edges, and there is no visual test that separates the weighted from the unweighted case. The classes are nonetheless different: a convex tiling is a power diagram exactly when it is the projection of a convex polyhedron, which is a genuine restriction, and it is a Voronoi diagram only under a further one. The eye cannot tell them apart and the lifting map can, which is the recurring pattern of this ladder.

Where this is the right model #

The construction earns its keep in three places, and in each of them the weights are physically meaningful rather than parameters to tune.

Foam. In a two-dimensional dry foam, the film between two bubbles is a curve whose curvature is set by the pressure difference, and equal pressures give a straight film — which is the unweighted bisector, arriving from physics rather than from geometry. Where the pressures are close the films are nearly straight, and the equilibrium structure is closely approximated by a power diagram in which each bubble’s weight encodes its pressure. Lloyd’s iteration on that diagram is one of the standard ways of relaxing a simulated foam, which ties this rung to the previous one.

Molecular surfaces. An atom is modelled as a sphere with a van der Waals radius, which turns a molecule into a packing of spheres of assorted sizes, and the accessible surface of a molecule is computed by dividing space between the spheres. Using distance divides it wrongly — a large atom and a small one meet halfway, which puts the boundary inside the large atom. Using power puts the boundary where the tangent lengths agree, which is where the spheres actually meet when they touch. The buried atoms are the ones with no cell, and they contribute no surface, which is the correct answer.

Optimal transport. Given a region and a set of target masses, the problem of cutting the region into pieces of exactly those masses while minimising total squared displacement has a solution, and the solution is always a power diagram — the weights are the dual variables of the mass constraints. That is a theorem rather than a modelling choice, and it is the reason power diagrams turn up in numerical transport, in fluid simulation, and in fair-division problems where the pieces must have prescribed sizes.

The transport case is worth one more sentence, because it inverts how the weights are usually thought about. In the foam and the molecule the weights are given by the physics and the diagram is computed from them. In transport the areas are given and the weights are unknown, and finding them is a convex optimisation whose objective is the very cost Lloyd’s iteration descends. So the same family of diagrams appears once as a model and once as the answer to a problem, and the second appearance is the reason the construction has a claim to being canonical rather than convenient. It is the same relationship a division into equal shares has to the prices that would produce it.

What it costs, and what it does not #

The cost is the loss of a guarantee, and it is worth stating precisely because it is the only thing that is genuinely harder.

The unweighted diagram of $n$ sites has $n$ cells, each containing its own site, and any algorithm can rely on that. The power diagram has at most $n$ cells, may have fewer, and a cell need not contain its own site — a site can sit outside its own territory when its neighbours are much larger. Both facts break the standard point-location shortcut of “find the nearest site”, because nearest is no longer the answer to the question being asked.

What does not cost anything is the computation. Constructing a power diagram is constructing a convex hull in three dimensions, which is exactly what constructing the unweighted diagram was, at the same $O(n \log n)$. Nobody pays for the generalisation, which is another sign that it is the natural one rather than an extension.

Who assembled it, and out of what #

The pieces are old and the assembly is recent, which is the same shape the lifting map had.

The power of a point with respect to a circle is in Euclid in substance and was given its name by Jacob Steiner in 1826, along with the radical axis and the observation that three circles have a common radical centre. None of that was about dividing a plane between sites; it was projective geometry, studied because circles and lines behave uniformly once power is the coordinate.

The diagram itself was written down repeatedly — by Fritz Aurenhammer in 1987 under the name power diagram, and independently in crystallography as the Laguerre tessellation, and in the study of foams as the radical Voronoi tessellation. The three literatures used three names for one object for years, which is the ordinary consequence of a construction being natural in several places at once.

What Aurenhammer supplied that the others did not is the characterisation: a tiling of the plane by convex polygons is a power diagram exactly when it is the projection of a convex polyhedron. That is a statement about which tilings are reachable rather than about how to build one, and it is why the construction is a class rather than a recipe.

What the picture cannot show #

The circles are not the cells and the drawing invites the confusion. A site’s circle has radius $\sqrt{w}$ and its cell is a polygon, and neither contains the other in general — a circle routinely spills across a boundary into a neighbour’s cell, which is correct and looks like an error. The circle is a device for reading the weight, not a region of ownership.

A negative weight is legal and undrawable. Nothing in the algebra requires $w$ to be positive; the boundary formula uses only differences, so subtracting a constant from every weight leaves the diagram unchanged, and a site can perfectly well carry a negative one. There is then no circle to draw, because its radius would be imaginary, and every figure here quietly restricts itself to positive weights for that reason alone.

And the foam is not really this. Real films meet in threes at a hundred and twenty degrees and are genuinely curved where the pressures differ. A power diagram gets the topology right and the geometry approximately right, and the figures above are a model of a foam rather than a picture of one.

Where the ladder goes next #

The rung above reads the triangulation as a graph rather than as a picture and finds a spanning tree already inside it, which is the result that makes several classical problems cheap.

Sideways, the radical axis is the same object as the line an inversion turns a circle into — both are what happens when a circle is treated as a linear object in disguise. A circle carrying a number that behaves linearly is also what makes every planar graph a pile of tangent circles work, which is the same trick spent on a different question. The buried site is a low-dimensional relative of a point inside a convex hull, which is exactly the condition for being a mixture of the others rather than a vertex.

What is worth carrying away #

The right generalisation is usually the one that makes the algebra simpler rather than the one that reads more naturally.

Multiplying by a weight is the repair anybody would try first, and it produces circular boundaries, non-convex cells and no theory. Subtracting a weight from the squared distance sounds artificial and is exactly right, because the square is what cancels and cancellation is what keeps the boundaries straight. The construction that looks like a technical convenience is the one that turns out to describe foam, molecular surfaces and optimal transport.

The habit worth taking is to try the repair that preserves the cancellation. Any expression of the form squared distance plus something linear is a plane in disguise; anything else is not, and the difference between them is the difference between a subject and a special case.