Introduction to Power Diagrams

Introduction

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.

Try It

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">Click a colored site to select it, then drag the <b>Weight</b> slider to watch its cell grow or shrink. A weight of 0 gives the standard Voronoi cell.</p>
<canvas id="canvas" width="460" height="300"></canvas>
<div class="controls">
  <label>
    <span id="sel-label">Select a site to adjust its weight</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 weights</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Power diagram (Laguerre–Voronoi): site s with weight w claims point p when
//   pow(p, s) = dist(p,s)^2 - w^2  is minimized over all sites.
// When all weights are equal, this reduces to the standard Voronoi diagram.
// Computed here by brute-force pixel assignment (O(W*H*n)) which is fast enough
// for the demo canvas; a production algorithm uses O(n log n) convex hull lifting.

const canvas = document.getElementById('canvas');
const ctx    = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// Five sites with fixed positions and initial weight 0
const PALETTE = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#6a4c93'];
const INIT_POS = [[115,90],[345,80],[230,190],[80,220],[380,230]];
const sites = INIT_POS.map((p, i) => ({ x: p[0], y: p[1], w: 0, color: PALETTE[i] }));

let selected = null;

// Build an offscreen pixel buffer for the Voronoi fill
function powerDist(px, py, s) {
  const dx = px - s.x, dy = py - s.y;
  return dx*dx + dy*dy - s.w*s.w;
}

function draw() {
  // Pixel-fill cells
  const img = ctx.createImageData(W, H);
  const data = img.data;
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      let best = Infinity, owner = 0;
      for (let i = 0; i < sites.length; i++) {
        const d = powerDist(x, y, sites[i]);
        if (d < best) { best = d; owner = i; }
      }
      const idx = (y * W + x) * 4;
      const c = hexToRgb(PALETTE[owner]);
      data[idx]   = c[0];
      data[idx+1] = c[1];
      data[idx+2] = c[2];
      data[idx+3] = 50; // light fill
    }
  }
  ctx.putImageData(img, 0, 0);

  // Draw border lines by detecting cell transitions
  for (let y = 1; y < H-1; y++) {
    for (let x = 1; x < W-1; x++) {
      const o = owner2d(x, y);
      if (owner2d(x+1, y) !== o || owner2d(x, y+1) !== o) {
        ctx.fillStyle = 'rgba(80,80,80,0.35)';
        ctx.fillRect(x, y, 1, 1);
      }
    }
  }

  // Draw sites + weight circles
  for (let i = 0; i < sites.length; i++) {
    const s = sites[i];
    const isSelected = (i === selected);

    if (s.w > 0) {
      ctx.beginPath();
      ctx.arc(s.x, s.y, s.w, 0, 2*Math.PI);
      ctx.strokeStyle = s.color;
      ctx.lineWidth = isSelected ? 2.5 : 1.5;
      ctx.setLineDash([5, 3]);
      ctx.stroke();
      ctx.setLineDash([]);
    }

    // Site dot
    ctx.beginPath();
    ctx.arc(s.x, s.y, isSelected ? 10 : 7, 0, 2*Math.PI);
    ctx.fillStyle = s.color;
    ctx.fill();
    ctx.strokeStyle = isSelected ? '#fff' : 'rgba(0,0,0,0.3)';
    ctx.lineWidth = isSelected ? 2.5 : 1.5;
    ctx.stroke();
  }
}

// Fast owner lookup for border drawing (recompute per pixel)
function owner2d(x, y) {
  let best = Infinity, o = 0;
  for (let i = 0; i < sites.length; i++) {
    const d = powerDist(x, y, sites[i]);
    if (d < best) { best = d; o = i; }
  }
  return o;
}

function hexToRgb(hex) {
  const v = parseInt(hex.slice(1), 16);
  return [(v >> 16) & 255, (v >> 8) & 255, v & 255];
}

// Click: select nearest site
canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const cx = (e.clientX - rect.left) * scaleX;
  const cy = (e.clientY - rect.top)  * scaleY;
  let best = Infinity, pick = -1;
  for (let i = 0; i < sites.length; i++) {
    const dx = cx - sites[i].x, dy = cy - sites[i].y;
    const d = dx*dx + dy*dy;
    if (d < best) { best = d; pick = i; }
  }
  selected = pick;
  const slider = document.getElementById('weight-slider');
  slider.disabled = false;
  slider.value = sites[selected].w;
  const lbl = PALETTE[selected];
  document.getElementById('sel-label').textContent =
    fmt('Site %selected%%v% weight: %w%', { selected: selected, v: 1, w: sites[selected].w });
  draw();
});

document.getElementById('weight-slider').addEventListener('input', e => {
  if (selected === null) return;
  sites[selected].w = +e.target.value;
  document.getElementById('sel-label').textContent =
    fmt('Site %selected%%v% weight: %w%', { selected: selected, v: 1, w: sites[selected].w });
  draw();
});

document.getElementById('reset-btn').addEventListener('click', () => {
  sites.forEach(s => s.w = 0);
  selected = null;
  const slider = document.getElementById('weight-slider');
  slider.disabled = true; slider.value = 0;
  document.getElementById('sel-label').textContent = 'Select a site to adjust its weight';
  draw();
});

draw();

<p class="hint">Click a colored site to select it, then drag the <b>Weight</b> slider to watch its cell grow or shrink. A weight of 0 gives the standard Voronoi cell.</p>
<canvas id="canvas" width="460" height="300"></canvas>
<div class="controls">
  <label>
    <span id="sel-label">Select a site to adjust its weight</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 weights</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Power diagram (Laguerre–Voronoi): site s with weight w claims point p when
//   pow(p, s) = dist(p,s)^2 - w^2  is minimized over all sites.
// When all weights are equal, this reduces to the standard Voronoi diagram.
// Computed here by brute-force pixel assignment (O(W*H*n)) which is fast enough
// for the demo canvas; a production algorithm uses O(n log n) convex hull lifting.

const canvas = document.getElementById('canvas');
const ctx    = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// Five sites with fixed positions and initial weight 0
const PALETTE = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#6a4c93'];
const INIT_POS = [[115,90],[345,80],[230,190],[80,220],[380,230]];
const sites = INIT_POS.map((p, i) => ({ x: p[0], y: p[1], w: 0, color: PALETTE[i] }));

let selected = null;

// Build an offscreen pixel buffer for the Voronoi fill
function powerDist(px, py, s) {
  const dx = px - s.x, dy = py - s.y;
  return dx*dx + dy*dy - s.w*s.w;
}

function draw() {
  // Pixel-fill cells
  const img = ctx.createImageData(W, H);
  const data = img.data;
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      let best = Infinity, owner = 0;
      for (let i = 0; i < sites.length; i++) {
        const d = powerDist(x, y, sites[i]);
        if (d < best) { best = d; owner = i; }
      }
      const idx = (y * W + x) * 4;
      const c = hexToRgb(PALETTE[owner]);
      data[idx]   = c[0];
      data[idx+1] = c[1];
      data[idx+2] = c[2];
      data[idx+3] = 50; // light fill
    }
  }
  ctx.putImageData(img, 0, 0);

  // Draw border lines by detecting cell transitions
  for (let y = 1; y < H-1; y++) {
    for (let x = 1; x < W-1; x++) {
      const o = owner2d(x, y);
      if (owner2d(x+1, y) !== o || owner2d(x, y+1) !== o) {
        ctx.fillStyle = 'rgba(80,80,80,0.35)';
        ctx.fillRect(x, y, 1, 1);
      }
    }
  }

  // Draw sites + weight circles
  for (let i = 0; i < sites.length; i++) {
    const s = sites[i];
    const isSelected = (i === selected);

    if (s.w > 0) {
      ctx.beginPath();
      ctx.arc(s.x, s.y, s.w, 0, 2*Math.PI);
      ctx.strokeStyle = s.color;
      ctx.lineWidth = isSelected ? 2.5 : 1.5;
      ctx.setLineDash([5, 3]);
      ctx.stroke();
      ctx.setLineDash([]);
    }

    // Site dot
    ctx.beginPath();
    ctx.arc(s.x, s.y, isSelected ? 10 : 7, 0, 2*Math.PI);
    ctx.fillStyle = s.color;
    ctx.fill();
    ctx.strokeStyle = isSelected ? '#fff' : 'rgba(0,0,0,0.3)';
    ctx.lineWidth = isSelected ? 2.5 : 1.5;
    ctx.stroke();
  }
}

// Fast owner lookup for border drawing (recompute per pixel)
function owner2d(x, y) {
  let best = Infinity, o = 0;
  for (let i = 0; i < sites.length; i++) {
    const d = powerDist(x, y, sites[i]);
    if (d < best) { best = d; o = i; }
  }
  return o;
}

function hexToRgb(hex) {
  const v = parseInt(hex.slice(1), 16);
  return [(v >> 16) & 255, (v >> 8) & 255, v & 255];
}

// Click: select nearest site
canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const cx = (e.clientX - rect.left) * scaleX;
  const cy = (e.clientY - rect.top)  * scaleY;
  let best = Infinity, pick = -1;
  for (let i = 0; i < sites.length; i++) {
    const dx = cx - sites[i].x, dy = cy - sites[i].y;
    const d = dx*dx + dy*dy;
    if (d < best) { best = d; pick = i; }
  }
  selected = pick;
  const slider = document.getElementById('weight-slider');
  slider.disabled = false;
  slider.value = sites[selected].w;
  const lbl = PALETTE[selected];
  document.getElementById('sel-label').textContent =
    fmt('Site %selected%%v% weight: %w%', { selected: selected, v: 1, w: sites[selected].w });
  draw();
});

document.getElementById('weight-slider').addEventListener('input', e => {
  if (selected === null) return;
  sites[selected].w = +e.target.value;
  document.getElementById('sel-label').textContent =
    fmt('Site %selected%%v% weight: %w%', { selected: selected, v: 1, w: sites[selected].w });
  draw();
});

document.getElementById('reset-btn').addEventListener('click', () => {
  sites.forEach(s => s.w = 0);
  selected = null;
  const slider = document.getElementById('weight-slider');
  slider.disabled = true; slider.value = 0;
  document.getElementById('sel-label').textContent = 'Select a site to adjust its weight';
  draw();
});

draw();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/power-diagram/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Power Diagrams

When weight rewrites the notion of distance