Voronoi Shattering

Drop a handful of pebbles onto still water and watch the ripples race outward. Each ripple claims every point it reaches before any other. When the fronts collide, they leave a network of boundaries — and that network is a Voronoi diagram.

A Voronoi diagram of a set of seed points partitions the plane into regions, one per seed, where every point in a region is closer to its seed than to any other seed. The boundary between two regions is the perpendicular bisector of the segment joining their seeds — the set of all points equidistant from both.

The geometry appears everywhere in nature: the hexagonal cells of a beehive, the cracks in dried mud, the spots on a giraffe, the territories of competing plant roots, even the large-scale structure of galaxies. When physical forces push outward from centers and compete for space, Voronoi geometry is the result.

Voronoi diagrams were first studied systematically by the Ukrainian mathematician Georgy Voronoi in 1908, and the efficient algorithm for computing them — sweeping a line across the plane — was discovered by Steven Fortune in 1987. Fortune's algorithm runs in $O(n \log n)$ time for $n$ seeds, which is optimal since sorting alone requires that much.

Click anywhere on the plate to add impact points (seeds). Each click shatters the surface along the Voronoi boundaries — the cracks run exactly where two seeds are equidistant. You can add up to 30 seeds; use Reset to start fresh with a blank plate.

<!-- {{c_html_intro}} -->
<div class="toolbar">
  <span class="hint-text">{{hint_text}}</span>
  <button id="btn-reset" type="button">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="480" height="360" title="{{canvas_title}}"></canvas>
<p class="seed-count" id="seed-count">{{seeds_label}}: 0</p>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.toolbar {
  display: flex;
  align-items: center;
  justify-content: space-between;
  margin-bottom: .5rem;
  gap: .5rem;
  flex-wrap: wrap;
}
.hint-text { font-size: .85rem; color: #555; flex: 1; }
button {
  font: 600 13px system-ui, sans-serif;
  padding: .35rem .8rem;
  border: 1px solid #1d3557;
  background: #1d3557;
  color: #fff;
  border-radius: 7px;
  cursor: pointer;
  white-space: nowrap;
}
button:hover { background: #16304e; }
/* {{c_canvas_style}} */
#canvas {
  display: block;
  width: 100%;
  max-width: 480px;
  border: 2px solid #c8d4de;
  border-radius: 10px;
  cursor: crosshair;
  touch-action: none;
}
.seed-count { font-size: .8rem; color: #777; margin: .4rem 0 0; }

// Code not found

Notice how every crack is a straight line segment — a piece of the perpendicular bisector between two seeds. Three cracks always meet at a single point (a Voronoi vertex), which is equidistant from exactly three seeds. The more seeds you add, the finer the fracture — just like real glass shatters into smaller fragments near an impact point.

Computing a Voronoi diagram from scratch looks deceptively expensive — after all, each of the $n$ seeds could in principle influence every other. But the structure is far more local than it appears.

• Naive approach: for each of infinitely many candidate boundary points, check which seed is closest — obviously impractical.
• Brute force for vertices: a Voronoi vertex is the circumcenter of three seeds. Try all $\binom{n}{3}$ triples, check that no other seed lies inside the circumcircle — $O(n^4)$ total.
• Fortune's sweepline (1987): a vertical line sweeps left to right. A beach line of parabolas (one per seed seen so far) tracks the advancing wavefront. Events — parabola intersections and circle events — are processed in a priority queue. Total time: $O(n \log n)$, space $O(n)$.
• Lower bound: $\Omega(n \log n)$ is provably optimal. Any algorithm that computes the Voronoi diagram can sort $n$ numbers (by placing seeds on a line), and sorting requires $\Omega(n \log n)$ comparisons.

The dual graph of a Voronoi diagram is the Delaunay triangulation: connect seeds whose Voronoi cells share an edge. Every triangle's circumcircle contains no other seed — this empty circumcircle property makes Delaunay triangulations maximize the minimum angle, avoiding slivers. The same structure solves the closest pair problem and underpins nearest-neighbor search trees.

Voronoi diagrams are one of the most versatile structures in computational geometry. Their applications span fields from telecommunications to biology:

• Wireless networks: each cell-tower's coverage zone is exactly its Voronoi cell — the region closer to it than to any rival tower. Planning tower placement to cover a city is a Voronoi optimization problem.
• Epidemiology: John Snow's 1854 cholera map implicitly used Voronoi regions to link deaths to water pumps — one of history's most famous data visualizations.
• Game AI and pathfinding: Voronoi roadmaps give moving agents natural corridors that stay as far as possible from all obstacles.
• Mesh generation for simulation: finite-element solvers need meshes that avoid sliver triangles; the dual Delaunay triangulation is the standard tool.
• Fracture simulation in film and games: shatter effects in movies and games (glass breaking, rock splitting) are rendered by computing Voronoi cells around random impact points, exactly as in our demo.
• Biology and ecology: animal territories, plant root competition, and the cells of living tissue all self-organize into approximate Voronoi patterns driven by proximity and resource competition.

Understanding the convex hull and Voronoi diagram together gives you the two most important proximity structures in computational geometry.

A Voronoi diagram emerges from the simplest possible rule: every point belongs to whichever seed is closest. From that one sentence flows the geometry of cracked mud, giraffe spots, cell towers, and shattered glass — and an $O(n \log n)$ algorithm that is provably as fast as it can be.

The next time you see a pane of glass crack into irregular shards, or dried earth split along ancient lines, you are watching Fortune's algorithm run in nature — each fragment the territory of the impact point that claimed it first. The math of breaking things apart turns out to be the math of belonging to the nearest neighbor.