Pin a handful of points to a flat surface — say, the centers of a few stores in your city. For every other point in the plane (every house, every park, every street corner), ask: which pinned point is closest?
The answer divides the plane into regions, one per pinned point. Each region contains exactly the locations whose nearest pinned point is that one. The boundaries of the regions are equidistant lines: along a boundary, two pinned points are equally close.
The whole picture is called a Voronoi diagram. It looks like this:
Each colored region is a Voronoi cell. The black dots are the sites. Anywhere inside a colored region, the nearest site is the dot in that region. The lines between regions are equidistant from two adjacent sites; the corners are equidistant from three.
Voronoi diagrams are one of the most studied objects in computational geometry. They have an extraordinary range of natural applications and surprisingly deep mathematical structure. This article is about what they are, how they’re computed, and where they show up.
Formal definition
For a set of points (called sites or generators) in the plane, the Voronoi cell of site is
In words: contains every point in the plane whose distance to is no greater than its distance to any other site. The Voronoi cell is the “domain of influence” of site .
The boundaries between cells are perpendicular bisectors of segments between sites: along the bisector of and , you’re equidistant from both. So the cell of is the intersection of half-planes, each bounded by a perpendicular bisector. Each cell is therefore a convex polygon.
The decomposition extends naturally to higher dimensions: in 3D you get Voronoi polyhedra, in D you get Voronoi cells in .
Where Voronoi diagrams appear
The applications are extraordinarily diverse.
Finding the nearest hospital, store, or service. If you have stores and want to assign each customer to their nearest store, the Voronoi diagram tells you which customers go where. This is the basic delivery-routing problem, the basic emergency-response problem, the basic public-service-allocation problem.
Cellular network coverage. Each cell tower has a Voronoi region — the geographic area where it’s the closest tower. Mobile phones connect to their Voronoi-nearest tower (with adjustments for signal strength). The “cells” in cellular networks are literally Voronoi cells.
Crystal structures. The atomic structure of metals and other crystalline solids has Voronoi-like decomposition. Each atom has a “Wigner-Seitz cell” containing all points closest to that atom. In ideal crystals, the cells are regular polyhedra (e.g., truncated octahedra in body-centered cubic).
Cell biology. The cells in many tissues — particularly epithelial cells — pack like Voronoi cells around their nuclei. Mathematical biology uses Voronoi models to analyze tissue growth, cancer spread, and morphogenesis.
Animal markings. Giraffe spots, leopard rosettes, and other complex animal markings can be modeled as Voronoi-like patterns. The biological mechanism (reaction-diffusion plus Voronoi-style competition) produces approximately Voronoi geometry.
Forest growth. Trees in mature forests often occupy Voronoi-like cells: each tree dominates the soil and light closest to it.
Ecology and territory. Animal territories often look Voronoi-shaped, since each animal defends a region around its home base.
Procedural generation. Video game maps, planetary surfaces in space games, and procedural textures often use Voronoi diagrams to generate naturalistic patterns. Worley noise — a Voronoi-based noise function — is widely used in shaders.
Robotics and motion planning. The “free space” in a robot’s environment is often analyzed via the Voronoi diagram of obstacles. The medial axis of free space (where multiple obstacles are equidistant) provides a clean path-planning structure.
Image segmentation and graphics. Voronoi-based methods segment images, generate stippling patterns (used in art), and produce mosaic effects.
This list is partial. The unifying theme: anytime you have a “nearest-of-many” problem in a continuous space, Voronoi diagrams are the natural mathematical structure.
The Delaunay dual
Every Voronoi diagram has a dual graph called the Delaunay triangulation. To form it, connect two sites with an edge whenever their Voronoi cells share an edge. The result is a triangulation of the sites — they’re divided into triangles, each containing no other site.
The red triangles are the Delaunay triangulation; the gray polygons in the background are the Voronoi cells. The two structures are dual: every Voronoi vertex corresponds to a Delaunay triangle, every Voronoi edge corresponds to a Delaunay edge, every Voronoi cell corresponds to a Delaunay site.
The Delaunay triangulation has a striking geometric property: it maximizes the minimum angle among all triangulations of the same sites. So Delaunay triangulations avoid sliver triangles (long, thin shapes), making them the preferred triangulation for finite-element simulations, mesh generation, and graphics.
Both Voronoi diagrams and Delaunay triangulations can be computed in time using algorithms like Fortune’s sweepline algorithm (1986) or randomized incremental insertion. These are standard tools in any computational geometry library.
Higher dimensions
The Voronoi/Delaunay duality extends to higher dimensions. In 3D, you get Voronoi polyhedra and Delaunay tetrahedralizations. In D, -cells and -simplices.
The 3D version is used:
- Crystallography: analyzing 3D crystal structures.
- Computer graphics: 3D mesh generation, particle effects.
- Astronomy: analyzing galaxy clustering on cosmological scales.
- Materials science: predicting properties of polycrystalline materials from grain shapes.
For very high dimensions, Voronoi diagrams become unwieldy: the number of cells and edges can grow exponentially with dimension. But low- to medium-dimensional Voronoi structures (up to 5–10D) are routinely used.
A subtler property: equilibrium
A Voronoi diagram can be viewed as the equilibrium of a competition. If “settlers” each claim the territory closest to them, the Voronoi diagram is the resulting partition.
Lloyd’s algorithm iterates this: starting from random sites, repeatedly:
- Compute the Voronoi diagram.
- Move each site to the centroid of its cell.
- Repeat.
This process converges to a “centroidal Voronoi tessellation” where each site sits at the center of its cell. The result is a remarkably regular partition that looks similar everywhere — even though it started from random points.
Centroidal Voronoi tessellations appear in:
- Stippling and halftone art: distributing dots evenly over an image.
- Mesh generation: producing meshes with uniform element size.
- Bird flocking and fish schools: equilibrium positions of agents avoiding each other.
A 19th-century geometric construction, when iterated, produces a 21st-century algorithm for evenly distributing things.
What Voronoi diagrams teach
The deepest lesson of Voronoi diagrams is that simple geometric questions can produce rich structure. The basic question — “what’s the closest site to each point?” — sounds elementary. The answer is a precise, computable, and astonishingly useful geometric structure.
This pattern recurs. Simple questions about points in space (closest, farthest, betweenness) generate the entire field of computational geometry: convex hulls, Voronoi diagrams, Delaunay triangulations, k-d trees, range searching. Each of these is a fundamental algorithm with thousands of applications.
For everyday users: Voronoi diagrams are everywhere once you know to look. The territories of cellular phone towers. The natural patterns on giraffes’ coats. The way trees space themselves in mature forests. The boundaries between countries in geopolitics often follow Voronoi-like nearest-neighbor patterns. The structure is so natural that it appears spontaneously, even without anyone designing it.
For applied mathematicians: Voronoi diagrams are a clean example of a geometric object whose definition is local but whose computation is global. You define each cell pointwise (the cell of a site is “everything closer to that site than to any other”), but to compute the diagram you need information from all sites at once. This local-to-global tension is characteristic of computational geometry.
A 1908 Ukrainian mathematician formalized something Descartes had noticed in 1644 and Dirichlet had touched on in 1850. The result is now a workhorse of modern engineering and a central object of computational geometry. Sometimes mathematics catches up to natural patterns. Sometimes it gets there first. With Voronoi, both happened simultaneously: the mathematics existed before the engineering, and engineering keeps finding new uses for it.
The next time you look at a giraffe, a cellular coverage map, or a procedurally-generated game world, you’re seeing a Voronoi diagram in action. The same mathematics, three different domains, one deep idea.
Frequently asked
Where did the name Voronoi come from?
Georgy Voronoy, a Ukrainian mathematician, formalized the concept in 1908. But the basic idea — dividing space by nearest-neighbor regions — had appeared earlier in Descartes (1644), Dirichlet (1850), and many natural-philosophy treatises. Voronoy's contribution was the systematic mathematical treatment, and his name stuck.
Are Voronoi diagrams useful in real life?
Yes. They're used to find the nearest hospital, identify cellular service coverage areas, model crystal grain structures, plan stores' delivery zones, generate procedural textures in computer graphics, analyze ecology of competing species, and design efficient data centers. Anytime you have a 'nearest-of-many-points' problem, Voronoi diagrams are the right tool.
What's the relationship between Voronoi diagrams and Delaunay triangulations?
They're dual to each other. The Delaunay triangulation connects pairs of sites whose Voronoi cells share an edge. Algorithmically, computing one gives you the other for free. Both are central data structures in computational geometry. Delaunay triangulations are particularly useful for mesh generation in finite-element methods.