What Is a Voronoi Diagram? Definition, Properties, History & Uses

The definition

Start with a set of points, called sites or seeds. The Voronoi cell of a site is every location that is at least as close to that site as to any other site. The cells together cover the whole plane without gaps or overlaps, so they form a tessellation.

cell(pₖ) = { x : d(x, pₖ) ≤ d(x, pⱼ) for every j ≠ k }

Figure 1. Move the pointer (or touch) over the figure. The line joins you to your nearest site, and the dashed circle shows that no other site is closer — that is why you are inside its cell.

Borders are perpendicular bisectors

Take any two sites. The points equally far from both form a straight line: the perpendicular bisector of the segment between them. Each border in a Voronoi diagram is a piece of such a bisector. A cell is what remains of the plane after cutting it, for every other site, along the bisector and keeping the side nearer to its own site — an intersection of half-planes, which is why every cell is convex.

Figure 2. Drag the three sites. Dashed lines are the full perpendicular bisectors; the solid lines are the parts that survive as Voronoi borders. They always meet at one point, the center of the circle through all three sites.

Key properties

Vertices are equidistant from three sites. Where three cells meet, the corner is the center of a circle passing through their three sites, and that circle contains no other site — the empty-circle property.
Cells are convex polygons. With straight-line distance, a cell never has a dent or a hole.
Outer cells are unbounded. A cell stretches to infinity exactly when its site lies on the convex hull of all the sites; that is why diagrams are usually clipped to a frame or a boundary.
About six neighbors per cell. A diagram of n sites has at most 3n − 6 edges and 2n − 5 vertices, so the average cell has fewer than six sides.
It is dual to the Delaunay triangulation. Joining every pair of sites whose cells share a border gives the Delaunay triangulation; the Voronoi vertices are the centers of its triangles' circumcircles.

Many names for one idea

The same construction was discovered again and again. Mathematicians say Voronoi diagram or Dirichlet tessellation; geographers and GIS users say Thiessen polygons; physicists call the cells around atoms in a crystal Wigner–Seitz cells, and the same cells in momentum space Brillouin zones. Computer scientists often just say nearest-neighbor regions.

A short history

1644 — René Descartes sketches the universe divided into vortex regions around stars, an informal early picture of the idea.
1850 — Peter Gustav Lejeune Dirichlet uses the construction in two and three dimensions while studying quadratic forms.
1854 — During the Broad Street cholera outbreak in London, John Snow maps deaths around water pumps; his map is often retold as an early nearest-facility analysis.
1908 — Georgy Voronoy defines the general construction in n dimensions, giving the diagram its name.
1911 — Meteorologist Alfred H. Thiessen uses the polygons to estimate rainfall over an area from scattered rain gauges.
1975–1986 — Computational geometry brings fast algorithms: Shamos and Hoey's divide-and-conquer method, the Bowyer–Watson Delaunay algorithm, and Fortune's sweep line, all running in O(n log n) time.

How Voronoi diagrams are computed

The simplest method intersects half-planes for each site, which gets slow for many sites. Practical software uses one of two fast approaches. Fortune's algorithm sweeps a line across the plane and maintains a "beach line" of parabolas — you can watch it in the Voronoi simulation. More commonly, a program first builds the Delaunay triangulation (for example with the Bowyer–Watson algorithm) and reads the Voronoi diagram off it; every tool on this site works that way. For curved or weighted variants, assigning each pixel to its nearest site is often the most practical method.

Where Voronoi diagrams are used

Urban planning and retail — catchment areas for schools, clinics, stores and fire stations.
Hydrology and climate — Thiessen polygons weight point measurements by the area they represent.
Telecommunications — the coverage area of each cell tower, before terrain and power are considered.
Biology and materials science — tissue cells, foams, grain structures in metals.
Robotics and games — paths that stay as far as possible from obstacles, and procedural maps.
Design and art — patterns, mosaics, stippling, architecture and 3D-printed lattices.

Variants

Changing one ingredient gives a whole family of diagrams. Give sites different strengths and you get weighted Voronoi diagrams and power diagrams. Measure distance along a street grid and you get Manhattan Voronoi diagrams. Compute on the globe and you get spherical Voronoi diagrams. Move every site to the center of its cell, again and again, and you reach a centroidal Voronoi tessellation.

Try it yourself

Frequently asked questions

What is a Voronoi diagram in simple terms?

Scatter some points on a page and color every spot by the point nearest to it. The colored regions are the cells of a Voronoi diagram; the lines between them are where two points are equally near.

What is the difference between Voronoi diagrams and Thiessen polygons?

None — they are the same construction. Voronoi diagram is the mathematical name; Thiessen polygons is the name used in geography, hydrology and GIS, after the meteorologist Alfred H. Thiessen.

Are Voronoi cells always convex?

Yes, with ordinary straight-line distance. Each cell is the intersection of half-planes, one for every other site, and an intersection of half-planes is always convex. With weights or other distance measures, cells can be curved or even split into pieces.

How many neighbors does a Voronoi cell have?

On average just under six. This follows from Euler's formula for planar graphs: a Voronoi diagram of n sites has at most 3n − 6 edges, so the average number of edges per cell approaches six as n grows.

How do I make a Voronoi diagram?

Use the free Voronoi diagram generator on this site: click to place points and the cells appear instantly. For real places, use the Voronoi map generator, which accepts coordinates and reports the area of each cell.

All Voronoi tools