Partitioning Space by Proximity
Given a set of seed points scattered across a plane, the Voronoi diagram draws the boundaries of influence — every location is assigned to its nearest seed. The resulting cells tile the plane with convex polygons, their edges equidistant from neighboring seeds. This deceptively simple construction encodes deep geometric and topological relationships.
Distance Metrics Matter
The standard Voronoi diagram uses Euclidean distance (p=2), producing familiar polygonal cells. Switch to Manhattan distance (p=1) and cells become diamond-shaped; use Chebyshev distance (p=∞) and they become square. The Minkowski exponent parameter in this simulator lets you morph between these geometries continuously, revealing how the distance metric shapes spatial perception.
Lloyd Relaxation and CVT
Random seed placement creates irregular cells of wildly varying sizes. Lloyd's algorithm fixes this: compute the Voronoi diagram, move each seed to its cell's centroid, repeat. After several iterations, cells converge to nearly equal area — a centroidal Voronoi tessellation. This is equivalent to k-means clustering, connecting computational geometry to machine learning's most basic algorithm.
From Crystals to Cell Towers
Voronoi diagrams appear everywhere in nature and engineering. Crystal grain boundaries form Voronoi cells around nucleation points. Giraffe skin patterns follow Voronoi tessellations. Cell phone networks optimize tower placement using weighted Voronoi diagrams. And in robotics, Voronoi roadmaps provide collision-free navigation paths through obstacle fields.