Partitioning Space by Proximity
A Voronoi diagram answers a simple question: given a set of seed points, which region of space is closest to each seed? The result is a beautiful partition of the plane into convex polygonal cells. Every point inside a cell is nearer to its seed than to any other. This fundamental construction appears throughout nature — from the patterns on a giraffe's skin to the territories of fish on a coral reef.
The Dual: Delaunay Triangulation
The Delaunay triangulation is the geometric dual of the Voronoi diagram. Connect two seeds whenever their Voronoi cells share an edge, and you get a triangulation with a remarkable property: no point lies inside the circumscribed circle of any triangle. This 'empty circle' property makes Delaunay triangulations optimal for mesh generation and interpolation.
From Nature to Algorithms
Fortune's sweep-line algorithm computes Voronoi diagrams in O(N log N) time. But nature computes them in parallel — crystal growth from multiple nucleation sites, the cracking pattern of dried mud, and the foam structure of soap bubbles all produce Voronoi-like patterns spontaneously through local physical processes.
Playing with Points
This simulation lets you add seed points and watch both the Voronoi diagram and Delaunay triangulation update in real time. Enable jitter to see how the diagram morphs as points move. Notice how the average number of cell neighbors converges to 6 — a consequence of Euler's formula for planar graphs that connects vertices, edges, and faces.