Voronoi Diagram

Voronoi diagram, also called a Dirichlet tessellation or Thiessen polygon decomposition, is a spatial partition in computational geometry and scientific computing that divides a metric space into proximity regions around a discrete set of generator points (sites). Given a finite set of n distinct generator sites P = {p₁, p₂, …, p_n} in a metric space (M, d), the Voronoi cell V(p_i) associated with site p_i consists of all points x ∈ M whose distance to p_i is no greater than their distance to any other site p_j ∈ P.

Visualized by René Descartes in 1644 to depict solar-system vortices, formalized by Peter Gustav Lejeune Dirichlet in 1850 for quadratic forms in ℝ² and ℝ³ and by Georgy Feodosevich Voronoy in 1908 for general dimension d, the Voronoi diagram is the geometric dual of the Delaunay triangulation. Across the sciences, Voronoi tessellations model crystal grain growth, Wigner–Seitz cells in solid-state physics, rainfall interpolation (Thiessen, 1911), ecological foraging, vector quantization in k-means clustering, and path planning for autonomous vehicles.

In d-dimensional Euclidean space ℝ^d equipped with the Euclidean norm d(x, y) = ‖x − y‖₂, the closed perpendicular bisector half-space of points closer to p_i than to p_j is:

H(p_i, p_j) = { x ∈ ℝ^d : ‖x − p_i‖₂ ≤ ‖x − p_j‖₂ } = { x ∈ ℝ^d : (p_j − p_i)^Tx ≤ (1/2)(‖p_j‖₂² − ‖p_i‖₂²) }.

The Voronoi cell V(p_i) is the intersection of the n − 1 closed half-spaces separating p_i from every other site:

V(p_i) = ⋂_j≠i H(p_i, p_j).

Because the intersection of closed convex half-spaces is a convex polyhedron, every Euclidean Voronoi cell V(p_i) is a (possibly unbounded) convex polygon in ℝ² or convex polyhedron in ℝ^d. Furthermore, a cell V(p_i) is unbounded if and only if p_i lies on the boundary of the convex hull conv(P).

Planar Graph Bounds via Euler's Formula

In the Euclidean plane ℝ² (for n ≥ 3 sites not all collinear), the boundaries of the Voronoi cells form a planar straight-line graph consisting of Voronoi edges (equidistant from two sites) and Voronoi vertices (equidistant from three or more sites, located at the circumcenters of triangles in the dual Delaunay triangulation). Compactifying unbounded rays onto a topological sphere and applying Euler's relation V − E + F = 2 with every Voronoi vertex having degree ≥ 3 yields linear bounds:

• Number of Voronoi vertices: at most 2n − 5
• Number of Voronoi edges: at most 3n − 6
• Average number of edges per Voronoi cell: less than 6 (approaching 6 for large interior meshes by Euler's hexagonal law).

Naively intersecting n − 1 half-planes for each of the n sites requires O(n² log n) time. In 1975, Michael Ian Shamos and Dan Hoey introduced the first optimal O(n log n) divide-and-conquer algorithm, and in 1986 Steven Fortune introduced Fortune's sweep-line algorithm, which computes the planar Voronoi diagram in O(n log n) time and O(n) space without divide-and-conquer merging.

The Parabolic Beach Line, Site Events, and Circle Events

As a horizontal sweep line ℓ moves downward across the plane, the Voronoi structure above ℓ cannot yet be finalized near ℓ because an unvisited site just below ℓ could still be closer to points slightly above ℓ. Fortune observed that the locus of points above ℓ equidistant from a visited site p_i (focus) and the sweep line ℓ (directrix) is a parabola opening upward. The lower envelope of all parabolas for sites above ℓ forms an x-monotonic curve of parabolic arcs called the beach line, whose breakpoints trace out the Voronoi edges as ℓ advances.

Fortune's algorithm maintains two data structures: a balanced binary search tree or skip list representing the ordered parabolic arcs along the beach line, and a priority queue of two types of discrete events:

1. Site event (when ℓ hits a new site p_i): A vertical parabolic arc of zero width is inserted into the beach line above p_i, splitting an existing arc into two and initiating a Voronoi edge.
2. Circle event (when ℓ reaches the bottom tangent of an empty circle through three consecutive beach-line sites p_i, p_j, p_k): The middle arc for p_j shrinks to zero and disappears, its two flanking breakpoints meet at a new Voronoi vertex (the circumcenter of Δp_ip_jp_k), and a new Voronoi edge between p_i and p_k begins.

Because there are n site events and at most 2n − 5 circle events, and each event performs O(log n) beach-line and priority-queue updates, total runtime is O(n log n).

A Voronoi diagram in which every generator site p_i coincides with the centroid of its own Voronoi cell V(p_i) with respect to a density function ρ(x),

p_i^* = [ ∫_V(pi) x ρ(x) dx ] / [ ∫_V(pi) ρ(x) dx ],

is called a Centroidal Voronoi Tessellation (CVT). CVTs minimize the expected quantization distortion energy E = ∑_i=1ⁿ ∫_V(pi) ‖x − p_i‖₂² ρ(x) dx. Lloyd's relaxation computes a CVT by alternating between constructing Vor(P) and moving each site to its cell's centroid—the continuous analog of k-means clustering—while Liu et al.'s quasi-Newton CVT method (2009) accelerates convergence using the Broyden–Fletcher–Goldfarb–Shanno algorithm (L-BFGS).

In epidemiology, John Snow's 1854 London cholera map corresponded to the Voronoi cell around the Broad Street water pump. In robotics, Voronoi edges among obstacles define the medial axis (maximum-clearance roadmap), along which a robot localized by a particle filter or Kalman filter maximizes obstacle clearance; in spatial clustering, inverse Voronoi cell volumes 1/|V(p_i)| provide point-density estimators that complement DBSCAN.

How does the Farthest-Point Voronoi Diagram find the minimum enclosing circle?

The farthest-point Voronoi diagram assigns each point x to the site p_i ∈ P that is farthest from x. Only sites on the convex hull conv(P) have non-empty farthest-point cells, and the tree of farthest-point Voronoi edges and vertices contains the center of the smallest enclosing circle of P, computable in O(n log n) time.

Why are Power Diagrams preferred over additively weighted Voronoi diagrams in 3D molecular modeling?

To model atoms of unequal van der Waals radii r_i, additively weighted distance ‖x − p_i‖₂ − r_i produces curved hyperboloid boundaries. The Power Diagram instead uses ‖x − p_i‖₂² − r_i², whose bisectors are flat radical planes, keeping every 3D cell a convex polyhedron with planar faces.

1. Voronoï, G. (1908). Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Journal für die reine und angewandte Mathematik, 134, 198–287. https://doi.org/10.1515/crll.1908.134.198
2. Fortune, S. (1987). A sweepline algorithm for Voronoi diagrams. Algorithmica, 2(1), 153–174. https://doi.org/10.1007/BF01840357
3. Aurenhammer, F. (1991). Voronoi diagrams—A survey of a fundamental geometric data structure. ACM Computing Surveys, 23(3), 345–405. https://doi.org/10.1145/116873.116880
4. Du, Q., Faber, V., & Gunzburger, M. (1999). Centroidal Voronoi tessellations: Applications and algorithms. SIAM Review, 41(4), 637–676. https://doi.org/10.1137/S0036144599352836