The Real Complexity of the Voronoi Diagram

Introduction

Pick a handful of points on the plane — call them sites: fire stations, cell towers, coffee shops, whatever you like. Now ask one question, over and over, for every other point in space: which site is closest to me?

Answer that question everywhere at once and something remarkable happens: the plane snaps into a patchwork of cells, one per site, where every location inside a cell is nearer to that site than to any other. That patchwork is the Voronoi diagram, named for the mathematician Georgy Voronoi, who studied it in 1908 (Descartes had sketched the same idea for planetary orbits centuries earlier).

The rule sounds almost too simple to be interesting — "closest wins" — yet it produces sharp straight-edged borders, sudden corners where three or more territories meet, and a structure so useful it shows up in biology, robotics, astronomy and your phone's cell-tower handoff. Drag a single site and, as you're about to see, the whole map redraws around it.

Drag the Sites

Click anywhere on the canvas to drop a colored site. Then grab any site and drag it — every pixel on the canvas is recolored to whichever site is currently nearest to it, live, as you move.

<p class="hint">Each colored dot is a <b>site</b>. Every pixel is shaded by whichever site is currently closest to it. Drag a site to see its cell — and every neighboring cell — redraw live.</p>
<canvas id="board" class="board" width="480" height="320"></canvas>
<div class="status" id="status">Drag a site, or add a new one.</div>
<div class="btns">
  <button id="addSite" type="button">Add random site</button>
  <button id="reset" 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; }
.board { display: block; width: 100%; max-width: 480px; height: auto; aspect-ratio: 480 / 320;
         border-radius: 10px; border: 1px solid #cdd9e3; cursor: crosshair; touch-action: none; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Voronoi diagram demo: for every pixel, find the nearest site (by squared
// Euclidean distance) and color it accordingly. Dragging a site just moves one
const canvas = document.getElementById('board');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const CELL = 6; // pixel block size for the coloring pass (bigger = faster, coarser borders)

// one fixed color per site, reused cyclically if more sites are added
const PALETTE = ['#e63946', '#1d3557', '#2a9d8f', '#e9c46a', '#8338ec', '#ff6d00', '#457b9d', '#d62828'];

let sites = [
  { x: 110, y: 90 },
  { x: 340, y: 70 },
  { x: 260, y: 210 },
  { x: 90, y: 250 },
];
let dragIndex = -1;

function dist2(ax, ay, bx, by) { const dx = ax - bx, dy = ay - by; return dx * dx + dy * dy; }

// Linear scan over all sites — O(n) per pixel, fine for a handful of sites.
function nearestSite(x, y) {
  let best = 0, bestD = Infinity;
  for (let i = 0; i < sites.length; i++) {
    const d = dist2(x, y, sites[i].x, sites[i].y);
    if (d < bestD) { bestD = d; best = i; }
  }
  return best;
}

function render() {
  // Coloring pass: recompute the nearest site for every block on the canvas.
  for (let py = 0; py < H; py += CELL) {
    for (let px = 0; px < W; px += CELL) {
      const owner = nearestSite(px + CELL / 2, py + CELL / 2);
      ctx.fillStyle = PALETTE[owner % PALETTE.length] + '33';
      ctx.fillRect(px, py, CELL, CELL);
    }
  }
  // Draw the site markers on top of their own cells.
  sites.forEach((s, i) => {
    ctx.beginPath();
    ctx.arc(s.x, s.y, 8, 0, Math.PI * 2);
    ctx.fillStyle = PALETTE[i % PALETTE.length];
    ctx.fill();
    ctx.lineWidth = 2;
    ctx.strokeStyle = '#fff';
    ctx.stroke();
  });
}

function canvasPoint(evt) {
  const rect = canvas.getBoundingClientRect();
  const cx = (evt.touches ? evt.touches[0].clientX : evt.clientX) - rect.left;
  const cy = (evt.touches ? evt.touches[0].clientY : evt.clientY) - rect.top;
  return { x: cx * (W / rect.width), y: cy * (H / rect.height) };
}

function setStatus(t) { document.getElementById('status').textContent = t; }

function pointerDown(evt) {
  const p = canvasPoint(evt);
  let hit = -1, hitD = 400; // squared pixel radius (~20px) to grab a site with the pointer
  sites.forEach((s, i) => { const d = dist2(p.x, p.y, s.x, s.y); if (d < hitD) { hitD = d; hit = i; } });
  dragIndex = hit;
  if (hit >= 0) setStatus('Dragging… release to drop the site.');
  evt.preventDefault();
}
function pointerMove(evt) {
  if (dragIndex < 0) return;
  const p = canvasPoint(evt);
  sites[dragIndex].x = Math.max(0, Math.min(W, p.x));
  sites[dragIndex].y = Math.max(0, Math.min(H, p.y));
  render();
  evt.preventDefault();
}
function pointerUp() {
  if (dragIndex >= 0) setStatus('Cell borders updated — every border sits exactly halfway between two sites.');
  dragIndex = -1;
}

canvas.addEventListener('mousedown', pointerDown);
canvas.addEventListener('mousemove', pointerMove);
window.addEventListener('mouseup', pointerUp);
canvas.addEventListener('touchstart', pointerDown, { passive: false });
canvas.addEventListener('touchmove', pointerMove, { passive: false });
window.addEventListener('touchend', pointerUp);

document.getElementById('addSite').addEventListener('click', () => {
  if (sites.length >= PALETTE.length) { setStatus('Palette full — reset to start over with fewer sites.'); return; }
  sites.push({ x: 40 + Math.random() * (W - 80), y: 40 + Math.random() * (H - 80) });
  render();
  setStatus(i18nFmt('Site #%n% added.', { n: sites.length }));
});
document.getElementById('reset').addEventListener('click', () => {
  sites = [
    { x: 110, y: 90 }, { x: 340, y: 70 }, { x: 260, y: 210 }, { x: 90, y: 250 },
  ];
  render();
  setStatus('Drag a site, or add a new one.');
});

render();

<p class="hint">Each colored dot is a <b>site</b>. Every pixel is shaded by whichever site is currently closest to it. Drag a site to see its cell — and every neighboring cell — redraw live.</p>
<canvas id="board" class="board" width="480" height="320"></canvas>
<div class="status" id="status">Drag a site, or add a new one.</div>
<div class="btns">
  <button id="addSite" type="button">Add random site</button>
  <button id="reset" 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; }
.board { display: block; width: 100%; max-width: 480px; height: auto; aspect-ratio: 480 / 320;
         border-radius: 10px; border: 1px solid #cdd9e3; cursor: crosshair; touch-action: none; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Voronoi diagram demo: for every pixel, find the nearest site (by squared
// Euclidean distance) and color it accordingly. Dragging a site just moves one
const canvas = document.getElementById('board');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const CELL = 6; // pixel block size for the coloring pass (bigger = faster, coarser borders)

// one fixed color per site, reused cyclically if more sites are added
const PALETTE = ['#e63946', '#1d3557', '#2a9d8f', '#e9c46a', '#8338ec', '#ff6d00', '#457b9d', '#d62828'];

let sites = [
  { x: 110, y: 90 },
  { x: 340, y: 70 },
  { x: 260, y: 210 },
  { x: 90, y: 250 },
];
let dragIndex = -1;

function dist2(ax, ay, bx, by) { const dx = ax - bx, dy = ay - by; return dx * dx + dy * dy; }

// Linear scan over all sites — O(n) per pixel, fine for a handful of sites.
function nearestSite(x, y) {
  let best = 0, bestD = Infinity;
  for (let i = 0; i < sites.length; i++) {
    const d = dist2(x, y, sites[i].x, sites[i].y);
    if (d < bestD) { bestD = d; best = i; }
  }
  return best;
}

function render() {
  // Coloring pass: recompute the nearest site for every block on the canvas.
  for (let py = 0; py < H; py += CELL) {
    for (let px = 0; px < W; px += CELL) {
      const owner = nearestSite(px + CELL / 2, py + CELL / 2);
      ctx.fillStyle = PALETTE[owner % PALETTE.length] + '33';
      ctx.fillRect(px, py, CELL, CELL);
    }
  }
  // Draw the site markers on top of their own cells.
  sites.forEach((s, i) => {
    ctx.beginPath();
    ctx.arc(s.x, s.y, 8, 0, Math.PI * 2);
    ctx.fillStyle = PALETTE[i % PALETTE.length];
    ctx.fill();
    ctx.lineWidth = 2;
    ctx.strokeStyle = '#fff';
    ctx.stroke();
  });
}

function canvasPoint(evt) {
  const rect = canvas.getBoundingClientRect();
  const cx = (evt.touches ? evt.touches[0].clientX : evt.clientX) - rect.left;
  const cy = (evt.touches ? evt.touches[0].clientY : evt.clientY) - rect.top;
  return { x: cx * (W / rect.width), y: cy * (H / rect.height) };
}

function setStatus(t) { document.getElementById('status').textContent = t; }

function pointerDown(evt) {
  const p = canvasPoint(evt);
  let hit = -1, hitD = 400; // squared pixel radius (~20px) to grab a site with the pointer
  sites.forEach((s, i) => { const d = dist2(p.x, p.y, s.x, s.y); if (d < hitD) { hitD = d; hit = i; } });
  dragIndex = hit;
  if (hit >= 0) setStatus('Dragging… release to drop the site.');
  evt.preventDefault();
}
function pointerMove(evt) {
  if (dragIndex < 0) return;
  const p = canvasPoint(evt);
  sites[dragIndex].x = Math.max(0, Math.min(W, p.x));
  sites[dragIndex].y = Math.max(0, Math.min(H, p.y));
  render();
  evt.preventDefault();
}
function pointerUp() {
  if (dragIndex >= 0) setStatus('Cell borders updated — every border sits exactly halfway between two sites.');
  dragIndex = -1;
}

canvas.addEventListener('mousedown', pointerDown);
canvas.addEventListener('mousemove', pointerMove);
window.addEventListener('mouseup', pointerUp);
canvas.addEventListener('touchstart', pointerDown, { passive: false });
canvas.addEventListener('touchmove', pointerMove, { passive: false });
window.addEventListener('touchend', pointerUp);

document.getElementById('addSite').addEventListener('click', () => {
  if (sites.length >= PALETTE.length) { setStatus('Palette full — reset to start over with fewer sites.'); return; }
  sites.push({ x: 40 + Math.random() * (W - 80), y: 40 + Math.random() * (H - 80) });
  render();
  setStatus(i18nFmt('Site #%n% added.', { n: sites.length }));
});
document.getElementById('reset').addEventListener('click', () => {
  sites = [
    { x: 110, y: 90 }, { x: 340, y: 70 }, { x: 260, y: 210 }, { x: 90, y: 250 },
  ];
  render();
  setStatus('Drag a site, or add a new one.');
});

render();

Result

Console

Watch the borders as you drag: each one sits exactly halfway between its two neighboring sites, perpendicular to the line joining them — the classic perpendicular bisector from geometry class. Push two sites close together and their shared border barely moves the ratio; drag one site across the canvas and its entire cell, and every cell touching it, reshapes to match.

The Real Complexity

The diagram looks like it should be expensive — every point in an infinite plane needs an answer. How is that tractable at all?

The naive approach tests every candidate point against all $n$ sites to find the nearest one — fine for a single query, disastrous for drawing the whole diagram pixel by pixel.
The clever approach is optimal. Steven Fortune's sweep-line algorithm (1987) sweeps a line across the plane and builds the entire diagram, all $n$ cells and their borders, in $O(n \log n)$ time using a beach-line data structure. That matches the $\Omega(n \log n)$ lower bound for the problem (it reduces to sorting), so nothing asymptotically faster is possible in general.
A single cell is easy on its own. One site's cell is just the intersection of $n-1$ half-planes, each one the "closer to me than to that other site" side of a perpendicular bisector — an idea explored on its own in convex hull construction.
Updates are the hard part. Rebuilding from scratch after moving one site still costs $O(n \log n)$ ; keeping a diagram valid under continuous motion (as in the demo above) is an active area called kinetic or dynamic Voronoi maintenance, and it is considerably trickier than the static case.
The dual is free. Connect any two sites whose cells share a border and you get the Delaunay triangulation — a whole extra structure that costs nothing extra to derive, explored in depth in Voronoi & Delaunay.

So this is one of computational geometry's genuine success stories: a question about infinitely many points collapses to a clean, provably optimal algorithm over just the $n$ sites.

Where It Matters

"Which site owns this point?" turns out to be one of the most quietly useful questions you can ask, so the diagram shows up everywhere:

Wireless networks: which cell tower should a phone hand off to? Its Voronoi cell, in effect, decides.
Machine learning: a nearest-neighbor classifier (see k-nearest neighbors) draws its decision boundary as the border of a Voronoi cell around each labeled example.
Robotics and motion planning: staying as far as possible from every obstacle means hugging the edges of the obstacles' Voronoi diagram — a classic collision-avoidance trick.
Epidemiology: John Snow's 1854 map of London cholera deaths around the Broad Street pump is, in hindsight, an informal Voronoi argument about which well served which household.
Crystallography and biology: Wigner–Seitz cells in solid-state physics and the territorial packing of plant cells and animal coat patterns both follow the same nearest-neighbor rule.

Learn this one partition and you've met the geometric skeleton behind nearest-neighbor search, closely tied to the closest pair problem that also hinges on "who is near whom."

Conclusion

The Voronoi diagram starts from a question a child could ask — "which one is closest?" — and turns it into a sharp, provably correct map of the entire plane, built in optimal $O(n \log n)$ time no matter how the sites are scattered.

It is also a gateway: flip the same picture over and you get the Delaunay triangulation for free (see Voronoi & Delaunay), and the same nearest-neighbor logic underlies classifiers, coverage maps and motion planners far beyond geometry class. Next time you drag a pin on a map and watch a coverage zone shift, you're watching a Voronoi cell move in real time.

Comments

Loading comments...

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

Cookies & privacy

The Voronoi Diagram

Every point in the plane picks its nearest neighbor