Voronoi diagram

A Voronoi diagram partitions a space into regions, each consisting of all points closer to one particular input site than to any other. Named after Georgy Voronoy, who studied them in 1908, these diagrams encode proximity relationships in a form that makes nearest-neighbor queries trivial: to find the closest site to a query point, simply locate which Voronoi cell contains it.

The construction of Voronoi diagrams in two dimensions can be achieved in O(n log n) time using Fortune's algorithm, a sweep-line method that generates the diagram by tracking a parabolic wavefront. This complexity bound is optimal because the diagram can be used to sort: given n numbers on a line, their Voronoi diagram encodes their ordering. The dual structure, the Delaunay triangulation, connects sites whose Voronoi cells share an edge and possesses the critical property that no input point lies inside the circumcircle of any triangle — a condition that produces well-shaped meshes for finite element analysis.

Voronoi diagrams generalize beyond Euclidean spaces to arbitrary metrics, weighted sites, and higher dimensions, though the complexity grows rapidly. In three dimensions, the diagram can have Ω(n²) complexity, and exact computation becomes numerically delicate due to predicate degeneracies. Despite these challenges, Voronoi diagrams remain indispensable in facility location, mesh generation, texture synthesis, and the analysis of spatial point patterns in ecology and epidemiology.