Voronoi Diagram

A Voronoi diagram is a fundamental geometric structure in computational geometry that divides a plane (or higher-dimensional space) into regions called Voronoi cells, each associated with a generating point (seed or site). Every location within a Voronoi cell is closer to its generating point than to any other generating point in the set. While mathematically equivalent to Thiessen polygonsThiessen PolygonsThiessen polygons (also known as Voronoi diagrams) partition a plane into regions based on proximity to a set of inpu..., the term Voronoi diagram emphasizes the broader mathematical and computational context of this spatial partitioning technique, which extends well beyond its original hydrological application.

Formally, given a set of n generating points in a plane, the Voronoi cell for point pi is the set of all locations x such that the distance from x to pi is less than or equal to the distance from x to any other generating point pj. The boundaries between adjacent cells are segments of perpendicular bisectors between neighboring generating points. The Voronoi diagram is the dual graph of the Delaunay triangulationDelaunay TriangulationDelaunay triangulation connects a set of points into a network of non-overlapping triangles such that no point lies i...: connecting generating points whose Voronoi cells share an edge produces the Delaunay triangulation. This duality relationship is exploited in computational algorithms, as constructing one structure yields the other. The mathematical properties of Voronoi diagrams have been studied extensively, revealing connections to optimization theory, crystallography, and spatial statistics.

The basic Voronoi diagram uses Euclidean distanceEuclidean DistanceEuclidean distance is the straight-line distance between two points in a plane, computed using the Pythagorean theore... and uniform weights, but numerous variants extend its applicability. Weighted Voronoi diagrams assign different weights to generating points, creating cells of unequal size that reflect facility capacity, attractiveness, or importance. Additively weighted Voronoi diagrams offset distances by a constant per point, useful for modeling facilities with different service radii. Multiplicatively weighted Voronoi diagrams scale distances, representing varying speeds or costs. Higher-order Voronoi diagrams assign locations to their k-nearest generating points rather than just the nearest one. Network Voronoi diagrams compute proximity along a road or transportation networkTransportation NetworkA Transportation Network is the interconnected system of roads, railways, waterways, and transit routes that enables ... rather than straight-line distance, producing more realistic service areas.

Voronoi diagrams are applied extensively across scientific and practical domains. Logistics and facility planning use Voronoi diagrams to define delivery zones, allocate customers to distribution centers, and optimize facility networks. Robotics and autonomous navigation use Voronoi diagrams of obstacles to compute maximum-clearance paths. Crystallography uses Voronoi cells (Wigner-Seitz cells) to describe the atomic structure of materials. Ecology applies Voronoi diagrams to model plant competition for resources based on proximity. Urban geography uses Voronoi diagrams to analyze the spatial structure of retail networks and service provision. Computer graphics employs Voronoi tessellation for procedural texture generation, mesh partitioning, and spatial data structures.

Voronoi diagrams provide a complete, non-overlapping partition of space that is uniquely determined by the generating points. They have well-understood mathematical properties and efficient computational algorithms (O(n log n) time complexity). The dual relationship with Delaunay triangulationDelaunay TriangulationDelaunay triangulation connects a set of points into a network of non-overlapping triangles such that no point lies i... provides access to both proximity-based partitioning and optimal triangulation from a single computation. Voronoi diagrams adapt naturally to any distribution of generating points without requiring regular grid structures.

Standard Voronoi diagrams assume uniform, isotropic space, which rarely reflects real-world geographic conditions with roads, barriers, and varying terrain. Dynamic updates when generating points are added, removed, or moved require careful algorithmic handling. Three-dimensional Voronoi diagrams are significantly more complex to compute and visualize. The sensitivity of cell boundaries to point positions means that small changes in input can produce large changes in the partition.

GPU-accelerated Voronoi computation enables real-time tessellation for interactive applications with thousands of generating points. Centroidal Voronoi tessellation, where generating points coincide with cell centroids, is being applied to optimal sampling and mesh generation. Integration with location-based servicesLocation-Based ServicesLocation-based services (LBS) are applications and platforms that use geographic location data from mobile devices to... enables dynamic Voronoi partitioning for ride-sharing, food delivery, and on-demand logistics. Voronoi-based spatial analysis is expanding into 3D applications including building interior modeling and airspace partitioning.