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:
“On every formal visit a child ought to be of the party, by way of provision for discourse.”
—Jane Austen (1775–1817)
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)