Introduction

Imagine scattering a handful of seed points across a map. Each point "owns" the region of the map closest to it โ€” no matter where you stand, you belong to the territory of whichever seed is nearest. Stitch those territories together and you get a Voronoi diagram: one of the most useful structures in computational geometry.

Voronoi diagrams show up everywhere โ€” mapping the nearest hospital in a city, routing signals in a sensor network, detecting collisions in a physics engine, or reconstructing surfaces from 3D scan data. Given n seed points, how quickly can we build this diagram?

A naive approach tests every point on the plane against all n seeds: impractical. A smarter brute-force builds each region one boundary edge at a time: O(n2)O(n^{2}). But in 1987, Steven Fortune published an algorithm that does it in O(nlogโกn)O(n \log n) โ€” optimal, because just sorting the seeds already costs that much. His trick is a deceptively simple idea: sweep a line across the plane.

Fortune's algorithm is classified as solved: it achieves the proven lower-bound complexity of ฮ˜(n log n) for Voronoi construction in the algebraic decision-tree model. No algorithm can do better in the worst case.

Watch the Sweepline

Click anywhere on the canvas to place seed points, then press Sweep to watch Fortune's algorithm work. The vertical line is the sweep line; the curved arcs below it form the beach line โ€” a frontier of parabolas, one per seed already processed. Every time two beach-line arcs collide or a new seed is hit, the algorithm records a Voronoi edge.

<div class="toolbar">
  <button id="btnSweep" type="button">Sweep</button>
  <button id="btnStep" type="button">Step</button>
  <button id="btnReset" type="button" class="ghost">Clear</button>
  <span class="hint-text">Click canvas to add seeds</span>
</div>
<canvas id="c" width="500" height="360"></canvas>
<div id="info" class="info-bar">Add seeds, then press Sweep or Step.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; background: #f8f9fb; }
.toolbar { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; padding: .4rem 0 .5rem; }
button { font: 600 13px system-ui; padding: .38rem .85rem; border-radius: 7px;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.hint-text { font-size: .82rem; color: #666; margin-left: .3rem; }
canvas { display: block; border: 1px solid #d0d8e4; border-radius: 8px;
         background: #fff; cursor: crosshair; touch-action: none; max-width: 100%; }
.info-bar { font-size: .88rem; color: #444; margin-top: .45rem; min-height: 1.3em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fortuneโ€™s sweepline algorithm โ€“ interactive Voronoi demo
// The demo runs an animated step-by-step sweep across seed points.
// For clarity we use a simplified event-driven simulation that correctly
// traces parabolic beach-line arcs and emits Voronoi edges.
//
// Key data structures:
//   sites  โ€“ array of {x,y} seed points
//   events โ€“ min-heap ordered by x (sweep goes leftโ†’right here, vertical line moves right)
//   beachLine โ€“ sorted array of arc segments (each arc is a parabola with focus = site)
//   edges โ€“ finished Voronoi half-edges {x1,y1,x2,y2}

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

// โ”€โ”€ Colours โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const C_SITE   = '#1d3557';
const C_EDGE   = '#457b9d';
const C_BEACH  = '#e63946';
const C_SWEEP  = '#2a9d8f';
const C_REGION = [
  '#dbe9f4','#fde8ea','#e8f5e9','#fff8e1',
  '#f3e5f5','#e0f2f1','#fce4ec','#e8eaf6'
];

let sites  = [];
let sweepX = -1;      // current sweep line x position
let edges  = [];      // finished edges [{x1,y1,x2,y2}]
let animId = null;
let stepMode = false;

// โ”€โ”€ Parabola helpers โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// A parabola with focus F = (fx,fy) and directrix x = d
// satisfies: (x - fx)^2 + (y - fy)^2 = (x - d)^2
// Solving for x given y: x = ((y-fy)^2 + fx^2 - d^2) / (2*(fx - d))
function parabolaX(fy, fx, d, y) {
  const denom = 2 * (fx - d);
  if (Math.abs(denom) < 1e-9) return fx; // degenerate (site on directrix)
  return ((y - fy) * (y - fy) + fx * fx - d * d) / denom;
}

// โ”€โ”€ Intersection of two beach-line parabolas (returns y coordinates) โ”€โ”€โ”€โ”€โ”€โ”€
// Given two sites A and B (both with focus to the left of sweep line d),
// find y coords where their parabolas intersect.
function intersectY(A, B, d) {
  // Quadratic: coefficients from (x_A(y) = x_B(y))
  const a1 = 1, b1 = -2*A.y, c1 = A.y*A.y + A.x*A.x - d*d;
  const a2 = 1, b2 = -2*B.y, c2 = B.y*B.y + B.x*B.x - d*d;
  // (a1-a2)y^2 + (b1-b2)y + (c1-c2) = 0  ... but a1=a2=1 so:
  // (b1-b2)y + (c1-c2) = 0  ... only if same coeff for y^2; actually need full:
  // expand: for site (fx,fy) with directrix d:
  // x = (y^2 - 2fy*y + fy^2 + fx^2 - d^2) / (2(fx - d)):
  //   x = (y^2 - 2fy*y + fy^2 + fx^2 - d^2) / (2(fx - d))
  // Setting x_A = x_B:
  //   (y^2-2Ay*y + Ay^2 + Ax^2 - d^2)(2(Bx-d)) = (y^2-2By*y + By^2 + Bx^2-d^2)(2(Ax-d))
  const dA = 2*(A.x - d), dB = 2*(B.x - d);
  if (Math.abs(dA) < 1e-9 && Math.abs(dB) < 1e-9) return [H/2];
  if (Math.abs(dA) < 1e-9) return [A.y];
  if (Math.abs(dB) < 1e-9) return [B.y];
  // coeff of y^2: dB - dA
  const qa = dB - dA;
  const qb = -2*A.y*dB + 2*B.y*dA;
  const qc = (A.y*A.y + A.x*A.x - d*d)*dB - (B.y*B.y + B.x*B.x - d*d)*dA;
  if (Math.abs(qa) < 1e-9) {
    if (Math.abs(qb) < 1e-9) return [H/2];
    return [-qc/qb];
  }
  const disc = qb*qb - 4*qa*qc;
  if (disc < 0) return [H/2];
  const sq = Math.sqrt(disc);
  return [(-qb - sq)/(2*qa), (-qb + sq)/(2*qa)];
}

// โ”€โ”€ Beach-line arc structure โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Each arc = { site: {x,y}, startY, endY }  (y range this arc owns on the sweep line)
// We rebuild the beach-line from scratch at each rendered frame for the animation.

function beachLineArcs(processedSites, d) {
  // Sort sites by x (already processed means site.x <= d)
  const active = processedSites.filter(s => s.x < d + 1e-9).slice();
  if (active.length === 0) return [];
  if (active.length === 1) return [{ site: active[0], startY: 0, endY: H }];

  // For each y, find which arc is frontmost (max x)
  // Build arc list by finding breakpoints between adjacent arcs sorted by y
  // This is a simplified O(n^2) beach-line rebuild for visualization
  const arcs = [];
  // Collect all breakpoint y-values
  const bps = new Set([0, H]);
  for (let i = 0; i < active.length; i++) {
    for (let j = i+1; j < active.length; j++) {
      const ys = intersectY(active[i], active[j], d);
      ys.forEach(y => { if (y > 0 && y < H) bps.add(y); });
    }
  }
  const sorted = [...bps].sort((a,b) => a-b);

  // For each segment between breakpoints, find the frontmost site
  for (let i = 0; i < sorted.length - 1; i++) {
    const yMid = (sorted[i] + sorted[i+1]) / 2;
    let maxX = -Infinity, bestSite = active[0];
    for (const s of active) {
      const x = parabolaX(s.y, s.x, d, yMid);
      if (x > maxX) { maxX = x; bestSite = s; }
    }
    // Merge with previous arc if same site
    if (arcs.length > 0 && arcs[arcs.length-1].site === bestSite) {
      arcs[arcs.length-1].endY = sorted[i+1];
    } else {
      arcs.push({ site: bestSite, startY: sorted[i], endY: sorted[i+1] });
    }
  }
  return arcs;
}

// โ”€โ”€ Full Voronoi via Fortuneโ€™s algorithm (simplified, O(n^2) for small n) โ”€
// Returns finished edges for a given set of sites
function fortuneVoronoi(sites) {
  const n = sites.length;
  if (n < 2) return [];
  const result = [];
  // For each pair of adjacent sites in vertical order, trace their shared edge
  // This is the correct full output for the completed diagram
  // We use the dual: build Delaunay by brute force, then extract Voronoi edges
  // For the demo scale (< 30 sites), O(n^3) Delaunay is fine

  // Build Delaunay triangulation via brute force (each triple, check circumcircle)
  function circumcircle(a, b, c) {
    const ax=a.x,ay=a.y,bx=b.x,by=b.y,cx=c.x,cy=c.y;
    const D = 2*(ax*(by-cy)+bx*(cy-ay)+cx*(ay-by));
    if (Math.abs(D) < 1e-9) return null;
    const ux=((ax*ax+ay*ay)*(by-cy)+(bx*bx+by*by)*(cy-ay)+(cx*cx+cy*cy)*(ay-by))/D;
    const uy=((ax*ax+ay*ay)*(cx-bx)+(bx*bx+by*by)*(ax-cx)+(cx*cx+cy*cy)*(bx-ax))/D;
    const r=Math.sqrt((ax-ux)*(ax-ux)+(ay-uy)*(ay-uy));
    return {cx:ux,cy:uy,r};
  }

  const triangles = [];
  for (let i=0;i<n;i++) for(let j=i+1;j<n;j++) for(let k=j+1;k<n;k++) {
    const cc = circumcircle(sites[i],sites[j],sites[k]);
    if (!cc) continue;
    // Check no other site inside circumcircle
    let valid = true;
    for (let l=0;l<n;l++) {
      if (l===i||l===j||l===k) continue;
      const dx=sites[l].x-cc.cx, dy=sites[l].y-cc.cy;
      if (dx*dx+dy*dy < cc.r*cc.r - 1e-6) { valid=false; break; }
    }
    if (valid) triangles.push([i,j,k,cc]);
  }

  // Voronoi edges are duals of Delaunay edges:
  // For each Delaunay edge (shared by two triangles), draw line between the two circumcenters
  // Build adjacency map
  const edgeMap = new Map();
  const key = (a,b) => a<b?`${a}-${b}`:`${b}-${a}`;
  triangles.forEach(([i,j,k,cc],ti) => {
    [[i,j],[j,k],[i,k]].forEach(([a,b]) => {
      const ek = key(a,b);
      if (!edgeMap.has(ek)) edgeMap.set(ek,[]);
      edgeMap.get(ek).push(ti);
    });
  });

  // Clip circumcenter to canvas bounds
  function clip(x,y) {
    return { x: Math.max(0, Math.min(W, x)), y: Math.max(0, Math.min(H, y)) };
  }

  edgeMap.forEach((tris, ek) => {
    if (tris.length === 2) {
      const cc1 = triangles[tris[0]][3];
      const cc2 = triangles[tris[1]][3];
      result.push({x1:cc1.cx,y1:cc1.cy,x2:cc2.cx,y2:cc2.cy});
    } else if (tris.length === 1) {
      // Boundary edge โ€” extend to canvas edge
      const cc1 = triangles[tris[0]][3];
      const [a,b] = ek.split('-').map(Number);
      const sa=sites[a], sb=sites[b];
      // Perpendicular bisector direction
      const mx=(sa.x+sb.x)/2, my=(sa.y+sb.y)/2;
      const dx=sb.x-sa.x, dy=sb.y-sa.y;
      const px=-dy, py=dx; // perpendicular
      // Extend in the direction away from circumcenter
      const len = 1000;
      // Pick direction so the edge goes "outward"
      const dot = (cc1.cx-mx)*px + (cc1.cy-my)*py;
      const sign = dot > 0 ? -1 : 1;
      const ex=cc1.cx+sign*px*len/Math.sqrt(px*px+py*py);
      const ey=cc1.cy+sign*py*len/Math.sqrt(px*px+py*py);
      result.push({x1:cc1.cx,y1:cc1.cy,x2:ex,y2:ey});
    }
  });
  return result;
}

// โ”€โ”€ Rendering โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function draw(d) {
  ctx.clearRect(0, 0, W, H);

  // Flood fill Voronoi regions
  if (sites.length > 0) {
    const imgData = ctx.createImageData(W, H);
    const colorList = C_REGION.map(hex => {
      const r=parseInt(hex.slice(1,3),16);
      const g=parseInt(hex.slice(3,5),16);
      const b=parseInt(hex.slice(5,7),16);
      return [r,g,b];
    });
    for (let py=0; py<H; py++) {
      for (let px=0; px<W; px++) {
        let minD=Infinity, idx=0;
        for (let i=0; i<sites.length; i++) {
          const dx=px-sites[i].x, dy=py-sites[i].y;
          const dd=dx*dx+dy*dy;
          if (dd<minD) { minD=dd; idx=i; }
        }
        const col = colorList[idx % colorList.length];
        const off = (py*W+px)*4;
        imgData.data[off]=col[0]; imgData.data[off+1]=col[1];
        imgData.data[off+2]=col[2]; imgData.data[off+3]=160;
      }
    }
    ctx.putImageData(imgData, 0, 0);
  }

  // Draw Voronoi edges (completed)
  ctx.save();
  ctx.strokeStyle = C_EDGE;
  ctx.lineWidth = 1.5;
  edges.forEach(e => {
    ctx.beginPath();
    ctx.moveTo(e.x1, e.y1);
    ctx.lineTo(e.x2, e.y2);
    ctx.stroke();
  });
  ctx.restore();

  // Draw beach line (parabolic arcs) up to sweep line
  if (d >= 0 && sites.length > 0) {
    const processed = sites.filter(s => s.x <= d);
    if (processed.length > 0) {
      const arcs = beachLineArcs(processed, d);
      ctx.save();
      ctx.strokeStyle = C_BEACH;
      ctx.lineWidth = 2;
      arcs.forEach(arc => {
        const s = arc.site;
        ctx.beginPath();
        let first = true;
        for (let y = arc.startY; y <= arc.endY; y += 1.5) {
          const x = parabolaX(s.y, s.x, d, y);
          if (x < 0 || x > W) continue;
          if (first) { ctx.moveTo(x, y); first = false; }
          else ctx.lineTo(x, y);
        }
        ctx.stroke();
      });
      ctx.restore();
    }

    // Draw sweep line
    ctx.save();
    ctx.strokeStyle = C_SWEEP;
    ctx.lineWidth = 2;
    ctx.setLineDash([6,4]);
    ctx.beginPath();
    ctx.moveTo(d, 0);
    ctx.lineTo(d, H);
    ctx.stroke();
    ctx.setLineDash([]);
    ctx.restore();
  }

  // Draw site points
  sites.forEach((s, i) => {
    ctx.save();
    ctx.fillStyle = d >= 0 && s.x <= d ? C_SITE : '#aaa';
    ctx.beginPath();
    ctx.arc(s.x, s.y, 5, 0, Math.PI*2);
    ctx.fill();
    ctx.restore();
  });
}

// โ”€โ”€ Animation โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let animSweepX = 0;
const SPEED = 2.5; // px per frame

function animate() {
  animSweepX += SPEED;
  sweepX = animSweepX;

  // Recompute edges up to current sweep position (for progressive reveal)
  const done = sites.filter(s => s.x <= sweepX);
  edges = fortuneVoronoi(done);

  draw(sweepX);
  const info = document.getElementById('info');
  const processed = done.length;
  info.textContent = fmt('Sweep at x=%round% โ€” processed %processed% of %length% sites', { round: Math.round(sweepX), processed: processed, length: sites.length });

  if (animSweepX < W) {
    animId = requestAnimationFrame(animate);
  } else {
    sweepX = -1;
    edges = fortuneVoronoi(sites);
    draw(-1);
    info.textContent = fmt('Done! Voronoi diagram for %length% site%v% computed in O(n log n).', { length: sites.length, v: sites.length!==1?'s':'' });
  }
}

function stopAnim() { if (animId) { cancelAnimationFrame(animId); animId = null; } }

// โ”€โ”€ Controls โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
document.getElementById('btnSweep').addEventListener('click', () => {
  if (sites.length < 2) {
    document.getElementById('info').textContent = 'Add at least 2 seed points first.';
    return;
  }
  stopAnim();
  animSweepX = 0;
  edges = [];
  stepMode = false;
  animate();
});

document.getElementById('btnStep').addEventListener('click', () => {
  if (sites.length < 2) {
    document.getElementById('info').textContent = 'Add at least 2 seed points first.';
    return;
  }
  stopAnim();
  stepMode = true;
  // Advance to next site event
  const sortedX = sites.map(s=>s.x).sort((a,b)=>a-b);
  if (sweepX < 0) sweepX = 0;
  const next = sortedX.find(x => x > sweepX + 1);
  if (next !== undefined) {
    sweepX = next + 1;
  } else {
    sweepX = W;
  }
  const done = sites.filter(s => s.x <= sweepX);
  edges = fortuneVoronoi(done);
  draw(sweepX < W ? sweepX : -1);
  const info = document.getElementById('info');
  if (sweepX >= W) {
    sweepX = -1;
    edges = fortuneVoronoi(sites);
    draw(-1);
    info.textContent = fmt('Done! Voronoi diagram for %length% site%v% computed.', { length: sites.length, v: sites.length!==1?'s':'' });
  } else {
    info.textContent = fmt('Step: sweep at x=%round% โ€” %length% of %length2% sites processed.', { round: Math.round(sweepX), length: done.length, length2: sites.length });
  }
});

document.getElementById('btnReset').addEventListener('click', () => {
  stopAnim();
  sites = []; edges = []; sweepX = -1; animSweepX = 0;
  draw(-1);
  document.getElementById('info').textContent = 'Add seeds, then press Sweep or Step.';
});

canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width;
  const scaleY = H / rect.height;
  const x = (e.clientX - rect.left) * scaleX;
  const y = (e.clientY - rect.top)  * scaleY;
  sites.push({ x, y });
  stopAnim();
  sweepX = -1; animSweepX = 0;
  edges = fortuneVoronoi(sites);
  draw(-1);
  document.getElementById('info').textContent =
    fmt('%length% seed%v% placed. Press Sweep to animate.', { length: sites.length, v: sites.length!==1?'s':'' });
});

// Add some default sites
[[100,80],[250,200],[380,90],[160,290],[420,260],[300,330],[80,200],[330,160]].forEach(([x,y]) => {
  sites.push({x,y});
});
edges = fortuneVoronoi(sites);
draw(-1);
document.getElementById('info').textContent =
  fmt('%length% seeds placed. Press Sweep to animate Fortuneโ€™s algorithm.', { length: sites.length });
Result
Console

Notice how the regions snap into place as the sweep progresses. The algorithm processes only two kinds of events โ€” site events (the sweep line reaches a seed) and circle events (three arcs meet at a point) โ€” and handles each in O(logโกn)O(\log n) time using a priority queue and a balanced binary tree. That is the source of the O(nlogโกn)O(n \log n) total cost.

The Real Complexity

Building a Voronoi diagram for n seeds sits in a well-understood corner of computational geometry:

  • Lower bound: any algorithm that constructs a Voronoi diagram must perform ฮฉ(n log n) comparisons in the worst case (algebraic decision-tree model). The proof reduces sorting to Voronoi โ€” if you could build the diagram faster, you could sort faster, contradicting the ฮฉ(n log n) lower bound for comparison-based sorting.
  • Fortune's algorithm achieves the bound: it runs in ฮ˜(n log n) time and O(n)O(n) space, making it asymptotically optimal.
  • The two event types: a site event fires when the sweep line hits a new seed, adding one parabolic arc to the beach line. A circle event fires when three consecutive arcs become co-circular, collapsing the middle arc and recording a Voronoi vertex. Both are handled in O(logโกn)O(\log n) via a heap and a balanced BST.
  • Connection to sorting: the tight link between sorting and Voronoi construction is why Fortune's result feels "final" โ€” not just fast, but provably unbeatable.

Fortune's algorithm is intimately related to Delaunay triangulation (the two structures are geometric duals of each other), and it is a canonical example of the sweepline paradigm that underlies many O(nlogโกn)O(n \log n) geometry algorithms.

Where It Matters

Voronoi diagrams are one of the most broadly useful data structures in applied geometry, and Fortune's algorithm is the standard way to build them:

  • Geographic information systems: nearest-facility queries (closest hospital, fire station, or polling place) are direct Voronoi lookups. Electoral district analysis often uses Voronoi regions as a fairness baseline.
  • Mesh generation and finite elements: engineering simulations need high-quality triangular meshes. The Delaunay triangulation โ€” the dual of the Voronoi diagram โ€” produces the "most equilateral" triangles possible, minimizing numerical error.
  • Collision detection in games and robotics: Voronoi regions define natural "lanes" through free space. A robot's roadmap through obstacles can be routed along Voronoi edges, maximizing clearance from walls.
  • Computer graphics and procedural generation: Worley noise (used for stone, cellular, and alien-skin textures) is directly the Voronoi distance function. Fortune's algorithm underlies efficient texture generation for large scenes.
  • Biology and materials science: Voronoi tessellations model cell growth, crystal grain boundaries, and the packing of biological tissue โ€” anywhere territory is claimed by nearest-center dynamics.

Because Fortune's algorithm is provably optimal and runs in linear space, it remains the go-to choice three decades after its publication. Understanding it means understanding the sweepline paradigm that also powers algorithms for closest pairs, interval scheduling, and geometric intersection.

Conclusion

Fortune's algorithm is a rare thing in computer science: a problem with a clean lower bound and an algorithm that meets it exactly. Sorting n numbers can't be done in fewer than ฮ˜(n log n) comparisons, and building the nearest-neighbor partition of a plane can't be done faster either โ€” the two problems are the same problem in disguise.

The sweepline idea โ€” advancing a line across the plane and maintaining just enough state to process events as they arrive โ€” is more than a trick for Voronoi diagrams. It is a general geometric technique that appears again and again in algorithms for closest pairs, intersections, and visibility. Fortune's 1987 paper introduced millions of programmers to the power of trading spatial reasoning for temporal order.

Next time a map app finds your nearest coffee shop in an instant, there's a good chance a Voronoi diagram โ€” and the ghost of Fortune's sweepline โ€” is quietly doing the geometry.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

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