The Voronoi Diagram

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.

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">{{hint_para}}</p>
<canvas id="board" class="board" width="480" height="320"></canvas>
<div class="status" id="status">{{status_idle}}</div>
<div class="btns">
  <button id="addSite" type="button">{{btn_add}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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 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.

"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."

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.