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.
Read more about this topic: Voronoi Diagram
Famous quotes containing the words formal and/or definition:
“Then the justice,
In fair round belly with good capon lined,
With eyes severe and beard of formal cut,
Full of wise saws and modern instances;
And so he plays his part.”
—William Shakespeare (1564–1616)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)