Power Diagrams

Imagine parceling a plane between several towns. The obvious rule — each point belongs to whichever town is nearest — gives you a Voronoi diagram: a mosaic of convex cells, one per town, where the borders run equidistant between neighbors.

But what if the towns are not equal? A big city has a longer reach than a hamlet. Give each town a weight and replace "distance" with power: for a point p and a site s with radius r, the power is the squared distance minus $r^{2}$. Now p belongs to whichever site has the smallest power over it.

The result is a power diagram (also called a Laguerre–Voronoi tessellation or additively-weighted Voronoi diagram). Geometrically, the boundaries are still straight lines — the diagram stays a convex partition — but heavier sites now claim more area, sometimes engulfing their lighter neighbors entirely.

Power diagrams were formally defined and analyzed by Franz Aurenhammer in 1987. He proved they can be computed in $O(n \log n)$ time in the plane — optimal, since you need at least that long just to sort the weights. The structure is solved: there are no open complexity questions here, but the geometry is rich and the applications are everywhere.

Five colored sites are placed on the canvas. Each has a weight — shown as the radius of the circle around it. The colored region shows the power cell: every pixel is assigned to whichever site minimizes its power distance.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="460" height="300"></canvas>
<div class="controls">
  <label>
    <span id="sel-label">{{sel_default}}</span>
    <input type="range" id="weight-slider" min="0" max="120" value="0" step="1" disabled>
  </label>
  <button id="reset-btn" type="button" class="ghost">{{reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#canvas { display: block; border-radius: 8px; border: 1px solid #cdd9e3;
          cursor: pointer; max-width: 100%; }
.controls { margin-top: .7rem; display: flex; align-items: center; gap: .8rem; flex-wrap: wrap; }
label { display: flex; align-items: center; gap: .5rem; flex: 1; min-width: 220px; font-size: .9rem; }
#sel-label { white-space: nowrap; min-width: 210px; font-weight: 600; }
input[type=range] { flex: 1; min-width: 100px; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Click any site to select it, then drag the Weight slider. Watch its circle and cell grow when you raise the weight and shrink when you lower it. A site with weight zero gets the same territory as a standard Voronoi cell; raise its weight high enough and it absorbs neighboring cells entirely. This is the same geometry that governs how bubbles in foam pack together and how weighted k-means clusters split a dataset.

Power diagrams sit comfortably in the solved category of computational geometry — the main theorem is tight and the algorithms are practical.

The lifting trick. Each site s with weight w maps to the paraboloid point (x, y, $x^{2}$+$y^{2}$−w) in 3-D. The lower convex hull of these lifted points, projected back down, is the power diagram. This reduces the problem to 3-D convex hull computation, which runs in $O(n \log n)$.

Aurenhammer's 1987 result showed:

• Computing the power diagram of n weighted sites in the plane takes $O(n \log n)$ time and $O(n)$ space.
• This is optimal: an Ω(n log n) lower bound follows from sorting (you can sort n numbers by embedding them as 1-D sites and reading off the diagram order).
• Every power cell is a convex polygon (possibly empty if a site's weight is dominated).
• The diagram is a valid cell decomposition: at most $O(n)$ edges and vertices in total.

Relation to other structures. The power diagram is a strict generalization of the Voronoi diagram (all weights equal → standard Voronoi) and of the furthest-site Voronoi diagram. When weights encode sphere radii, the diagram gives the exact sphere-packing contact structure in 2-D. In higher dimensions the same lifting map generalizes, giving $O(n ⌈d/2⌉)$ complexity via the upper bound theorem on convex polytopes.

There are no famous open problems attached to the basic power diagram — unlike P vs NP or the Riemann hypothesis, the structure is mathematically tame. The interesting questions today live in applications: optimal transport, weighted Delaunay refinement, and the geometry of foams.

Whenever influence is unequal, a power diagram is the right partition:

• Sphere packings and foams: in a random packing of spheres with different radii, the power diagram gives the exact contact graph — which spheres touch which. The wet-foam model (Laguerre foam) uses power cells directly as bubble shapes.
• Weighted clustering: replacing Euclidean distance with power distance in k-means lets clusters have different "reach," naturally handling groups of very different densities.
• Optimal transport (Wasserstein distances): the semi-discrete optimal transport problem amounts to finding a power diagram whose cells have prescribed areas (or volumes in 3-D). This powers fast algorithms for style transfer, texture synthesis, and point-cloud shape matching.
• Geographic market areas: retail chains with stores of different sizes use power-diagram models to estimate each store's natural catchment area, accounting for store capacity as the weight.
• Mesh generation: weighted Delaunay refinement (the dual of the power diagram) produces high-quality computational meshes for finite-element simulation.
• Protein structure analysis: the protein structure community uses power diagrams (with atomic van der Waals radii as weights) to decompose molecular surfaces and compute buried surface areas.

In each case the $O(n \log n)$ algorithm is fast enough for real data, and the convexity guarantee keeps the geometry tractable.

The power diagram is a small but elegant idea: replace distance with power — squared distance minus weight — and suddenly each site can claim territory in proportion to its importance. The boundaries stay straight, the cells stay convex, and an $O(n \log n)$ algorithm via a 3-D lifting map computes the whole thing optimally.

Unlike many structures in computational complexity, the power diagram has no open algorithmic questions; its complexity is settled. What keeps it alive is the breadth of phenomena it models — sphere packings, foam geometry, optimal transport, weighted clustering — all unified by a single reweighted notion of proximity.

Next time you watch soap bubbles cluster into uneven cells, you are looking at a power diagram. The bigger the bubble, the more territory it claims — and computing exactly which pixel belongs to which bubble takes only $O(n \log n)$ time.