The idea: the nearest post office
A town has 7 post offices, the sites. Every house wants the nearest one. Colour each house by its nearest office and the town splits into regions, one per office. These regions are the Voronoi cells, and together they form the Voronoi diagram. The cell of a site is every point that is closer to that site than to any other site.
The page uses the sites A (3, 3), B (9, 2), C (16, 3), D (10, 7), E (4, 10), F (15, 11) and G (9, 12) in a 20 × 14 box. The box only cuts the picture: the real diagram covers the whole plane.
Nearest site by brute force
For one query point Q, measure its distance to every site and keep the smallest. Comparing d² = dx² + dy² gives the same answer as comparing d, so no square root is needed. Q1 (13, 9) has d² = 8 to F and 13 to D, so it is in F's cell (Demo: nearest site to one point). That costs n distances per query.
Do it for many points and the cells appear. The page colours 41 × 29 = 1189 grid points this way, 8323 distances in all (Demo: colour every grid point). Some grid points are exactly as far from two sites. They are tied, and they lie on an edge of the diagram.
Bisectors and half-planes
For two sites s and t, the points equally far from both form a line: the perpendicular bisector of s and t. It goes through their midpoint at right angles to the segment st. One side of it is closer to s, the other closer to t.
So the cell of s is what is left after cutting the plane with the bisector of s and every other site and keeping s's side each time. It is the intersection of n − 1 half-planes, and an intersection of half-planes is always convex. The page starts with the box and cuts it six times (Demo: D's cell from 6 bisectors). D's cell ends with 6 corners. Each cut is a polygon clip: corners on the wrong side are dropped, and the two crossing points are added.
Not every bisector matters. For A, the bisectors with G, C and F miss the cell: after the three nearer sites, the cell is already closer to A than to them (Demo: A's cell is unbounded).
Vertices and empty circles
Where three cells meet, a point is equally far from three sites. That point is a Voronoi vertex, and it is the centre of the circle through the three sites. No other site is inside that circle, or that site would be nearer and the point would be in its cell. This is the empty circle property.
The 7 sites have 6 vertices and 12 edges. Each edge separates two cells; at each vertex three cells meet.
Unbounded cells
A site on the convex hull of the sites has a cell that goes on forever: walk away from the other sites and you keep getting closer to it. A, B, C, F, G and E are on the hull, so their cells reach the box edge. D is inside the hull, so its cell is a closed hexagon. The hull is explained in convex hull: Graham scan vs gift wrapping.
The Delaunay dual
Join two sites when their cells share an edge. The result is the Delaunay triangulation: one triangle per Voronoi vertex, one Delaunay edge per Voronoi edge, and each Delaunay edge is at right angles to its Voronoi edge. The two structures are duals: build one and you have the other. Here the triangles are ABD, ADE, BCD, CDF, DEG and DFG (Demo: the whole diagram, then the Delaunay dual).
Among all triangulations of the sites, Delaunay maximises the smallest angle, so it avoids thin triangles. That is why meshes for simulation and terrain use it.
Building it fast
| Method | Cost | How |
|---|---|---|
| Colour grid points | points × n | Brute force on a sample; only an image |
| Half-plane cuts per site | O(n²) to O(n² log n) | What Build Cell does, for every site |
| Fortune's sweep | O(n log n) | A line sweeps the plane; a beach line of parabolas traces the edges |
| Dual of Delaunay | O(n log n) | Build the Delaunay triangulation, then take the circumcentres |
With the diagram built, a nearest-site query becomes point location: find the cell that holds Q, in O(log n) with a search structure. In practice many programs use a k-d tree instead; see k-d trees and R-trees and k-nearest neighbours.
Where it is used
Nearest hospital, school or cell tower; the area each store serves; the regions of a k-means clustering (each cluster is the Voronoi cell of its centre); mesh generation through Delaunay; and procedural textures and maps in games. A grid of cells for "what is near me" is shown in quadtrees and geohashes.
Join sites whose cells share an edge and you get the dual: see Delaunay Triangulation.
What the page leaves out
The page does not animate Fortune's sweep line or the beach line, and it builds Delaunay by testing every triple, not with an incremental or divide-and-conquer algorithm. It skips degenerate input (four sites on one circle, where a vertex has four cells, or all sites on one line), floating-point robustness, other distances (Manhattan, weighted, power diagrams), Voronoi diagrams of segments, and higher dimensions.
See where this page fits on the Geometric Algorithms mind map.