Voronoi Diagram - Formal Definition

Formal Definition

Let be a space (a nonempty set) endowed with a distance function . Let be a set of indices and let be a tuple (ordered collection) of nonempty subsets (the sites) in the space . The Voronoi cell, or Voronoi region, associated with the site is the set of all points in whose distance to is not greater than their distance to the other sites, where is any index different from . In other words, if denotes the distance between the point and the subset, then

The Voronoi diagram is simply the tuple of cells . In principle some of the sites can intersect and even coincide (an application is described below for sites representing shops), but usually they are assumed to be disjoint. In addition, infinitely many sites are allowed in the definition (this setting has applications in geometry of numbers and crystallography), but again, in many cases only finitely many sites are considered.

In the particular case where the space is a finite dimensional Euclidean space, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are convex polytopes and they can be represented in a combinatorial way using their vertices, sides, 2-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. However, in general the Voronoi cells may not be convex or even connected.