A Voronoi diagram is a subdivision of a space into regions associated with a collection of objects called sites. Each region consists of the locations that are at least as close to its site as to any other site. In its standard form, the sites are points in a plane and closeness is measured by ordinary Euclidean distance. The result is a mosaic of convex polygonal regions, some extending indefinitely. More general constructions use different distance measures, weighted sites, curves, surfaces, or spaces of higher dimension.
Voronoi diagrams turn the question “Which site is nearest?” into a geometric structure. Their boundaries identify locations where nearest-site assignments change, while their vertices record ties among several sites. These properties make them fundamental in computational geometry and useful in spatial analysis, scientific computing, materials modeling, and data analysis. Their relationship with Delaunay triangulations connects nearest-neighbor geometry to mesh generation, interpolation, and the geometry of empty circles and spheres.
Definition and elementary geometry
Let be a finite set of distinct sites in Euclidean space . The closed Voronoi cell belonging to is
The cells collectively cover the space. Their interiors are disjoint, but their boundaries can overlap because a boundary point may have two or more equally near sites. Thus, “partition” is often used geometrically rather than as a strictly disjoint set partition. A prescribed tie-breaking rule can assign boundary points to individual cells when a disjoint assignment is required.
The boundary between the regions associated with two sites lies on their perpendicular bisector. Expanding squared distances gives
Every pairwise comparison therefore defines a closed half-space, and a cell is the intersection of these half-spaces. Consequently, every ordinary Euclidean point-site cell is a convex set. In two dimensions it is a possibly unbounded convex polygon; in three dimensions it is a possibly unbounded convex polyhedron. A site lies strictly inside its own cell because its distance from itself is zero and all other sites are distinct.
For example, consider sites , , and . The cell of is the region , . The cell of satisfies and , while that of satisfies and . All three meet at , the circumcenter of the triangle formed by the sites. Although the three pairwise bisectors are complete lines, only appropriate portions of them belong to the diagram: on the remaining portions, the third site is closer.
In a nondegenerate planar diagram, an edge consists of points having exactly two nearest sites, and a vertex has exactly three nearest sites. Four or more cocircular sites can instead produce a vertex incident to four or more cells. A cell is unbounded precisely when its site lies on the boundary of the convex hull of the sites. Collinear sites give a particularly simple diagram of parallel strips and two outer half-planes, with no finite Voronoi vertices.
Applications frequently restrict the diagram to a bounded study region , replacing each cell by . This operation is called clipping or restriction. A convex study region preserves cell convexity, whereas a nonconvex region can split a restricted cell into disconnected pieces. Boundaries introduced by clipping belong to the study region rather than to the nearest-site geometry itself.
Delaunay duality and higher-dimensional structure
The most important companion structure is the Delaunay triangulation. For planar sites in general position, two sites are joined by a Delaunay edge exactly when their Voronoi cells share an edge. Each Voronoi vertex corresponds to a Delaunay triangle whose circumcenter is that vertex. This is a geometric form of duality: sites correspond to cells, Delaunay edges to Voronoi edges, and Delaunay triangles to Voronoi vertices.
The defining property of a Delaunay triangle is that its open circumdisk contains no site. At the corresponding Voronoi vertex, its three sites are equally distant and no other site is nearer. Conversely, an empty circumcircle through three sites determines a Voronoi vertex when no additional site lies on the circle. The Delaunay edge connecting two neighboring sites is perpendicular to the associated Voronoi edge, but their finite segments need not intersect. In particular, an obtuse Delaunay triangle has its circumcenter outside the triangle.
General-position assumptions make the dual a triangulation without ambiguity. If four sites lie on an empty circle, their Voronoi cells can meet at one vertex, and the corresponding Delaunay face is a quadrilateral. Either diagonal triangulates that face while preserving the empty-open-circle property. The more intrinsic object is therefore a Delaunay subdivision, with a triangulation obtained by resolving nonsimplicial faces. Arbitrary diagonal choices can matter in software that compares combinatorial structures, even though the underlying Voronoi diagram is unchanged.
Planarity sharply limits the size of the two-dimensional diagram. For noncollinear sites, with no four cocircular and with sites on the convex hull, the numbers of finite Voronoi vertices and Voronoi edges are
Here edges include unbounded rays. These formulas follow from planar counting relations associated with the Euler characteristic and from the fact that a general-position Delaunay triangulation has triangular bounded faces. In particular, the planar diagram has linear combinatorial complexity.
A useful higher-dimensional interpretation lifts each site onto the paraboloid
Projecting the lower faces of the lifted convex hull gives the Delaunay subdivision. This connects nearest-site geometry with convex-hull algorithms and explains why empty spheres replace empty circles in higher dimensions. The favorable planar size bound does not persist: for fixed dimension , the worst-case combinatorial complexity can grow as . In three dimensions it can already be quadratic, so constructing a complete diagram may be expensive even when individual nearest-neighbor queries are manageable.
Historical development
The construction predates its modern terminology. René Descartes’s Principles of Philosophy, published in 1644, included a vortex-based account of matter with space-filling regions around centers. Such illustrations are often cited as an early precursor to Voronoi-like subdivisions. They were not a modern mathematical theory of nearest-site cells, and the resemblance should be distinguished from the later precise distance-based definition.
A direct mathematical treatment appeared in the work of Peter Gustav Lejeune Dirichlet in 1850. In studying quadratic forms, Dirichlet considered regions determined by proximity to lattice points. A lattice repeats under translations, so its nearest-point regions are translated copies of a fundamental cell. This setting connects the construction to number theory and the geometry of numbers rather than to the irregular finite point sets common in modern spatial computing. The name “Dirichlet domain” remains standard in several branches of geometry.
Georgy Voronoy developed the theory further in work published in 1908, particularly for higher-dimensional lattices and the classification of quadratic forms. His name became attached to the broader nearest-site construction, usually anglicized as “Voronoi.” Transliteration varies, so “Voronoy” also appears in historical and mathematical writing. Although the modern diagram is commonly introduced in the plane, the work central to its naming concerned a substantially more general mathematical setting.
An independently influential application arose in meteorology. In 1911, Alfred H. Thiessen described a method for estimating average precipitation over an area using polygonal regions assigned to rain gauges. Each gauge represented the portion of the study area closer to it than to another gauge. The resulting area-weighted average became known as the Thiessen polygon method. This established a practical vocabulary that remains common in hydrology and geographic information systems, even though the underlying geometry is the same as an ordinary planar Voronoi diagram.
Boris Delaunay’s 1934 work established the empty-sphere subdivision now associated with his name, making the dual relationship central to the subject. During the 1970s and 1980s, computational geometry transformed these constructions into standard algorithmic objects. Michael Shamos and Dan Hoey presented an influential planar divide-and-conquer approach in 1975; Steven Fortune’s 1987 paper introduced the widely used sweepline algorithm. Subsequent development emphasized robust geometric predicates, weighted and higher-dimensional variants, dynamic updates, and large-scale implementations. These developments brought together mathematical traditions that had originated in quadratic forms, spatial measurement, and discrete geometry.
Construction algorithms and numerical robustness
A direct construction follows immediately from the half-space definition: for each site, begin with the whole space or a bounding region and intersect it with the half-spaces induced by all other sites. This method is conceptually transparent and useful for small inputs or clipped cells. It considers quadratically many pairwise comparisons across all sites, however, and straightforward polygon clipping can involve additional work. More sophisticated planar algorithms exploit the linear size of the final diagram and achieve time, using standard asymptotic notation.
A divide-and-conquer algorithm sorts the sites, splits them into two groups, constructs their diagrams recursively, and merges them along a boundary separating regions nearer to the left group from regions nearer to the right group. With a linear-time merge, the recurrence is , yielding . An alternative constructs the Delaunay triangulation first and then obtains Voronoi vertices as circumcenters and Voronoi edges from adjacent triangles. The dual route is especially convenient when a software system already maintains a triangulation.
Fortune’s algorithm sweeps a line across the plane. Between the processed sites and the sweep line lies a “beach line” made of parabolic arcs: each arc describes points equidistant from a site and the current sweep line. Site events introduce arcs as new sites are encountered. Circle events remove arcs when a potential Voronoi vertex is reached. A balanced search structure maintains the beach line, and a priority queue maintains events. The resulting algorithm uses time and space under the usual computational assumptions. Invalidated circle events must be detected because later site events can change the local beach-line configuration.
Randomized incremental methods provide another important approach. Sites are inserted in random order, and the affected part of the diagram or triangulation is updated. With appropriate point-location and history structures, planar Delaunay construction has expected time. Dynamic insertion is often local in typical data, but worst-case updates can affect many cells. Deletion is more involved because the region previously occupied by a site must be reconstructed from its neighbors.
Reliable implementations must distinguish combinatorial decisions from approximate coordinate calculations. Orientation tests determine which side of a line a point occupies; incircle tests determine whether a point lies inside a circumcircle. Both can be expressed using determinants. Near-collinear or near-cocircular data can cause ordinary floating-point arithmetic to return an incorrect sign, producing inconsistent adjacency or invalid topology. Exact predicates, adaptive-precision arithmetic, and consistent symbolic perturbation address these failures. Exact decisions do not automatically make computed circumcenter coordinates accurate: nearly collinear triples can have very distant, numerically sensitive circumcenters. Degeneracy handling and coordinate accuracy are therefore related but distinct implementation problems.
Alternative distances, weights, and sites
The nearest-site definition extends naturally to a metric space :
The geometry depends strongly on the distance. Under Manhattan distance, , shortest paths reflect coordinate-wise travel, and bisectors are piecewise linear. Under maximum-coordinate distance, , metric balls are axis-aligned squares in two dimensions. Unlike the Euclidean case, some non-strictly convex metrics permit two distinct sites to have an equidistance region with nonempty interior. Tie conventions can therefore change more than a set of boundary curves.
A particularly useful weighted construction is the power diagram. Assign a real weight to site and compare power values
The cell of consists of points minimizing . Pairwise equality still reduces to a linear equation, so power cells remain convex polyhedra. A weighted site can have an empty cell, and its cell need not contain its location. If , the power expression also has the classical interpretation of the power of a point relative to a sphere of radius . The dual structure is called a regular triangulation.
Other weighting conventions produce different diagrams. Additive distance weights compare ; in the plane their bisectors are generally hyperbolic. Multiplicative weights compare , where ; their bisectors are generally circles or lines, and cells need not be convex or connected. These models cannot be substituted for power diagrams merely by relabeling the weights. Each convention encodes a different mechanism, such as an initial time advantage, a propagation speed, or a squared-distance preference.
Sites need not be points. Distance to a line segment, polygon, or surface is usually defined as the minimum distance to any point of that object. Voronoi diagrams of segments contain curved as well as straight edges. A polygon’s medial axis is closely related: it consists of interior locations with more than one nearest boundary point and can be characterized using centers of maximal inscribed disks. Segment-site Voronoi constructions provide a way to compute such skeletal representations, with special treatment of boundary features and endpoints.
Further variants alter either the query or the surrounding space. An order- diagram records the set of nearest sites rather than only the nearest one. A farthest-site diagram selects sites maximizing distance and depends only on convex-hull sites. Geodesic diagrams measure shortest-path distance around obstacles or along surfaces; network diagrams use shortest paths on a graph. Euclidean straight-line boundaries and convexity generally disappear in these settings. Their usefulness comes precisely from representing movement constraints or surface geometry that ordinary planar distance ignores.
Random tessellations and spatial statistics
When sites are random, their Voronoi diagram becomes a random geometric object. The best-studied model uses a homogeneous Poisson point process of intensity : a region of area contains a Poisson-distributed number of sites with mean , and counts in disjoint regions are independent. In the infinite plane this produces a stationary, isotropic Poisson–Voronoi tessellation. Its statistical behavior models irregular spatial competition without imposing an underlying grid.
Several useful quantities follow directly from the Poisson model. If is the distance from a fixed location to the nearest site, then exactly when the disk of radius around that location is empty. Consequently,
and
These formulas describe distance from an independently chosen location, not distance from one site to every point in its cell. Scaling lengths by removes the intensity parameter, so many dimensionless shape statistics are independent of .
For the typical cell selected through a typical generating site, the mean area is . In the planar Poisson–Voronoi model, the mean number of sides is six. The latter result reflects planar incidence relations and the fact that almost surely three cells meet at each vertex. It does not mean that the tessellation is predominantly a regular hexagonal tiling: individual cells vary widely in area, side count, elongation, and edge lengths. Many full distributions, including the cell-area distribution, do not have comparably simple closed forms and are studied through bounds, approximations, and simulation.
A crucial distinction separates the typical cell from the cell containing a uniformly sampled location. The second sampling procedure favors larger cells, because they occupy more area. Its distribution is therefore area-biased relative to that of the typical site-associated cell. Confusing these sampling schemes can lead to incorrect statements about average territory size or typical spatial experience. The distinction is an instance of a broader issue in statistics: the observation procedure changes the distribution being measured.
Observed tessellations also require careful treatment of boundaries. Cells intersecting the edge of an observation window are only partially visible; treating their clipped areas as full areas biases shape and size summaries. Periodic boundary conditions, guard regions, or appropriate edge corrections address different versions of this problem. Departures from the Poisson model are informative: repulsive site processes tend to produce more regular cells, while clustered processes produce combinations of dense small cells and large sparse regions. Voronoi statistics can quantify these patterns, but a fitted tessellation alone does not establish the physical process responsible for them.
Centroidal diagrams, clustering, and quantization
A centroidal Voronoi tessellation is a Voronoi diagram in which each site coincides with the centroid of its own cell, calculated with respect to a specified density. For a bounded domain and nonnegative density , define
This energy measures the total squared error incurred by representing every location by its nearest site. A density can express population, sampling importance, or another spatial weight rather than physical mass.
The centroid condition follows from two complementary minimizations. If the sites are fixed, assigning each point to its nearest site minimizes its contribution to squared distance. If the regions are fixed, their optimal representatives are their weighted centroids:
provided the denominator is positive. Under suitable regularity assumptions, a stationary configuration therefore satisfies the centroid condition. It need not be a global minimum, and different stationary arrangements can have different energies.
Lloyd’s algorithm alternates these two steps: construct the Voronoi cells, then move each site to its cell centroid. Each exact step does not increase the squared-distance energy. The method is associated with Stuart Lloyd’s work on least-squares quantization at Bell Laboratories in 1957, published in 1982. Its discrete counterpart is the standard Lloyd iteration for k-means clustering, where data points are assigned to the nearest cluster center and centers are replaced by cluster means. Empty clusters require a separate convention because their means are undefined.
The same mathematics underlies vector quantization. A finite codebook represents a continuous or high-resolution signal space; encoding selects the nearest codeword, and each codeword’s decision region is a Voronoi cell. Under a squared Euclidean loss function, minimizing expected distortion gives the centroid condition. Changing the distortion changes the decision regions and the optimal update rule, so not every quantizer is described by an ordinary Euclidean centroidal diagram.
For uniform planar density and many sites away from boundaries, low-energy configurations commonly approach locally hexagonal patterns. A triangular arrangement of sites produces regular hexagonal Voronoi cells, offering efficient and nearly isotropic coverage. This observation does not establish a universal hexagonal optimum for arbitrary domains, finite site counts, densities, or dimensions. Boundaries and spatially varying density introduce defects and unequal cell sizes. In high-resolution squared-error models in dimension , the asymptotically optimal density of sites scales as , rather than directly as . Regions with greater importance receive more representatives, but the allocation also reflects how approximation error decreases as cells become smaller.
Applications and limits of the nearest-site model
In geographic information systems, Voronoi cells provide service territories, proximity zones, and spatial aggregation units. The Thiessen rainfall estimate is
where is precipitation measured at gauge and is the area of its cell inside the catchment. The method assigns each location the value of its nearest gauge. It is therefore a piecewise-constant spatial model, not a reconstruction of atmospheric dynamics or terrain effects. Similar assignments appear in facility analysis, but straight-line proximity need not match travel time, capacity, or actual use.
Voronoi geometry also supports smoother interpolation. In natural-neighbor interpolation, a query point is temporarily inserted into the site set. Its new Voronoi cell takes area from neighboring cells, and the stolen areas define weights for their data values. This produces a local interpolant whose neighborhood adapts to the spatial arrangement. It differs fundamentally from assigning only the nearest observation, while still using the same geometric structure to identify relevant neighbors.
In scientific computing, paired Delaunay and Voronoi meshes are useful for finite-volume methods. A Voronoi cell serves as a control volume, and the line between adjacent sites is normal to their shared face. For isotropic diffusion, this orthogonality supports simple two-point approximations to normal flux. Conservation follows by using equal and opposite fluxes across shared faces. Strongly anisotropic diffusion, difficult boundaries, or nonorthogonal modifications require more elaborate discretizations; Voronoi geometry alone does not guarantee accuracy or stability for every differential equation.
In materials modeling, sites can represent nucleation centers. If all centers appear simultaneously and expand isotropically at the same speed through a homogeneous medium, first-arrival regions are ordinary Voronoi cells. Different nucleation times or growth speeds lead to weighted or otherwise generalized constructions. In atomistic analysis, three-dimensional cells describe local environments and coordination, with power diagrams accommodating particle-size differences. A Voronoi neighbor is a geometric neighbor, however, not automatically a chemical bond; small faces and perturbations can change the inferred coordination.
Robotics uses Voronoi edges as routes that balance distance from nearby obstacles. For polygonal obstacles, generalized diagrams and medial-axis constructions identify corridors with locally high clearance. A robot with nonzero size requires an appropriate free-space representation, often obtained by expanding obstacles before planning. Meanwhile, computer graphics uses nearest-site distance fields for cellular textures, procedural stone patterns, fracture-like subdivisions, and spatial sampling. A visually cellular pattern is not necessarily evidence of a physical Voronoi-generating process.
For data retrieval, the diagram is the geometric decision map of nearest-neighbor classification, but explicitly constructing it is often unnecessary. Tree-based indexes, approximate search, and direct distance calculations may be preferable, especially under the curse of dimensionality. Across these applications, the decisive modeling question is the meaning of “nearest”: Euclidean distance, travel cost, weighted arrival time, and similarity in a feature space define different assignments and support different interpretations.