Voronoi diagram
A plane partition into regions closest to given points.
A Voronoi diagram is a partition of a plane into regions close to each of a given set of objects, also classified as a tessellation. In the simplest case, these objects are finitely many points in the plane, called seeds, sites, or generators, with each seed having a corresponding Voronoi cell comprising all points closer to that seed than to any other. The diagram is named after mathematician Georgy Voronoy and is also called a Voronoi tessellation, Voronoi decomposition, Voronoi partition, or Dirichlet tessellation.
- Field
- Mathematics
- Known for
- Voronoi diagram
- Also named after
- Georgy Voronoy, Peter Gustav Lejeune Dirichlet, Alfred H. Thiessen
- Alternative names
- Voronoi tessellation, Voronoi decomposition, Voronoi partition, Dirichlet tessellation, Thiessen polygons
Lore & Background
The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation after Peter Gustav Lejeune Dirichlet. Voronoi cells are also known as Thiessen polygons, after Alfred H. Thiessen. In the simplest case, a finite set of points in the Euclidean plane is given, and each point has a corresponding cell consisting of points for which it is the nearest site. The boundary between two cells is the perpendicular bisector of the line segment joining the two sites, and each cell is a convex polygon formed by the intersection of half-spaces.
Reader's Guide
The Voronoi diagram has practical and theoretical applications in many fields, mainly in science and technology, but also in visual art. In the simplest case, given a finite set of points in the Euclidean plane, each point has a corresponding Voronoi cell consisting of points in the plane for which that point is the nearest site. The diagram is dual to the Delaunay triangulation of the set of points. When two cells share a boundary, it is a line segment, ray, or line of points equidistant to their two nearest sites. Vertices occur where three or more boundaries meet, at points with three or more equally distant nearest sites. The formal definition extends to any metric space with a tuple of nonempty subsets as sites, where the Voronoi cell is the set of points whose distance to its site is not greater than to any other site. In finite-dimensional Euclidean space with finitely many distinct point sites, Voronoi cells are convex polytopes, though in general they may not be convex or even connected.
Did You Know?
- The Voronoi diagram is also called a Dirichlet tessellation after Peter Gustav Lejeune Dirichlet.
- The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.
Frequently Asked Questions
Who is the Voronoi diagram and where does the name come from?
The Voronoi diagram is a mathematical partition of a plane into regions, each region collecting every point that is nearest to one particular seed (also called a site or generator). It takes its name from the Ukrainian mathematician Georgy Voronoy, though the idea was independently explored by others.
What are the Voronoi diagram's core 'powers' or function?
Its defining rule is simple: every point in the plane belongs to the cell whose seed is closest to it, so the whole plane is carved into non-overlapping polygons (or unbounded regions). This makes it a natural tool for answering 'which object is nearest?' questions across the entire plane.
What other names does the Voronoi diagram go by in the canon?
You'll also see it called a Voronoi tessellation, Voronoi decomposition, Voronoi partition, Dirichlet tessellation, or Thiessen polygons. All of these labels refer to the same fundamental plane-partitioning construction.
Why is the Voronoi diagram considered a landmark in mathematics?
It provides a geometrically exact way to divide space by proximity, which underpins algorithms in computational geometry, spatial statistics, crystallography, and many applied fields. Its elegance lies in turning a simple distance comparison into a complete tiling of the plane.
Who else is the Voronoi diagram historically linked to?
Beyond Voronoy himself, the construction is also credited to Peter Gustav Lejeune Dirichlet and to meteorologist Alfred H. Thiessen, whose work on rainfall maps popularized the same partitioning idea. This shared lineage is why the diagram carries multiple eponymous names.
More in Ukrainian inventions 1-23
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced