Voronoi

Voronoi diagrams, also called Voronoi tessellations, are a way of partitioning a plane into regions based on distance to a set of seed points. Each seed has a corresponding Voronoi cell consisting of all points closer to that seed than to any other seed. The boundaries between cells are formed by loci of points equidistant to two neighboring seeds, and the corners are points equidistant to three or more seeds.

Properties include that, in the plane, each cell is a convex polygon and the collection of edges forms a planar straight-line graph. A common related construct is the Delaunay triangulation, which is the dual graph to the Voronoi diagram: two seeds are connected by a Delaunay edge if and only if their Voronoi cells share an edge. The Delaunay triangulation has properties that maximize minimum angles in many cases.

History and variants: The concept is named after Georgy Voronoi, who studied it in 1907. Variants include farthest-point Voronoi diagrams, where regions correspond to sites farthest away, and weighted diagrams such as power diagrams or Apollonius diagrams, where distances are adjusted by weights.

Applications and computation: Voronoi diagrams appear in diverse areas such as meteorology, ecology, urban planning, computer graphics, robotics, and wireless network design. They are computed by algorithms such as Fortune's sweep line, divide-and-conquer, or incremental constructions, with typical time complexities near O(n log n). The concept extends to higher dimensions, where cells are convex polytopes.