Voronoidiagram

A Voronoidiagram is a partition of the plane into regions based on a finite set of sites. Each region contains all points that are closer to its associated site than to any other site. The collection of these regions forms the Voronoidiagram for the given set of sites.

For a pair of sites, the boundary between their regions lies on the locus of points equidistant to both sites, which is a straight line perpendicular to the segment joining the sites. Consequently, the edges of a Voronoidiagram are segments, rays, or lines; a cell is typically a convex polygon and a cell can be unbounded when the corresponding site lies on the convex hull of the set.

Geometric dual: the Voronoidiagram is closely related to the Delaunay triangulation of the same set of sites. If two sites share a Voronoidiagram edge, they are connected by a Delaunay edge. The circumcenters of Delaunay triangles are the vertices of the Voronoidiagram. The Delaunay triangulation tends to avoid skinny triangles and is widely used in mesh generation and spatial analysis.

Generalizations include higher dimensions and variations such as weighted Voronoidiagrams (additively or multiplicatively weighted), known as Apollonius diagrams, and diagrams for non-point sites such as lines or circles. These extensions are used in different applications where distance metrics or site shapes differ from the standard Euclidean point-site model.

Computationally, efficient algorithms exist (for example Fortune’s sweep line) to construct a Voronoidiagram in near-linear time. Practical implementations are available in many computational geometry libraries. Voronoidiagrams have applications in geography, meteorology, ecology, robotics, computer graphics, and spatial analysis for nearest-neighbor queries, clustering, and mesh generation.