Voronoi diagram

In mathematics, a Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points (called seeds, sites, or generators) is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation.

It is named after Georgy Voronoi, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi diagrams have practical and theoretical applications to a large number of fields, mainly in science and technology but also including visual art. They are also known as Thiessen polygons.

In the simplest case, shown in the first picture, we are given a finite set of points {p₁, …, p_n} in the Euclidean plane. In this case each site p_k is simply a point, and its corresponding Voronoi cell R_k consists of every point in the Euclidean plane whose distance to p_k is less than or equal to its distance to any other p_k. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.

Let ${\displaystyle \scriptstyle X}$ be a metric space with distance function ${\displaystyle \scriptstyle d}$. Let ${\displaystyle \scriptstyle K}$ be a set of indices and let ${\displaystyle \scriptstyle (P_{k})_{k\in K}}$ be a tuple (ordered collection) of nonempty subsets (the sites) in the space ${\displaystyle \scriptstyle X}$. The Voronoi cell, or Voronoi region, ${\displaystyle \scriptstyle R_{k}}$, associated with the site ${\displaystyle \scriptstyle P_{k}}$ is the set of all points in ${\displaystyle \scriptstyle X}$ whose distance to ${\displaystyle \scriptstyle P_{k}}$ is not greater than their distance to the other sites ${\displaystyle \scriptstyle P_{j}}$, where ${\displaystyle \scriptstyle j}$ is any index different from ${\displaystyle \scriptstyle k}$. In other words, if ${\displaystyle \scriptstyle d(x,\,A)\;=\;\inf\{d(x,\,a)\mid a\,\in \,A\}}$ denotes the distance between the point ${\displaystyle \scriptstyle x}$ and the subset ${\displaystyle \scriptstyle A}$, then

...
Wikipedia