Voronoi diagram

http://www.cs.sunysb.edu/~algorith/files/voronoi-diagrams.shtml

Input Description: A set S of points p_1,...,p_n.


Problem: Decompose the space into regions around each point, such that all the points in the region around p_i are closer to p_i than any other point in S.



http://en.wikipedia.org/wiki/Voronoi_diagram

In mathematics, a Voronoi diagram is a special kind of decomposition of a metric space determined by distances to a specified discrete set of objects in the space, e.g., by a discrete set of points.



In the simplest case, we are given a set of points S in the plane, which are the Voronoi sites. Each site s has a Voronoi cell, also called a Dirichlet cell, V(s) consisting of all points closer to s than to any other site. The segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi nodes are the points equidistant to three (or more) sites.

One of the early applications of Voronoi diagrams was by John Snow to study the epidemiology of the 1854 Broad Street cholera outbreak in Soho, England. He showed the correlation between areas on the map of London using a particular water pump, and the areas with most deaths due to the outbreak.
A point location data structure can be built on top of the Voronoi diagram in order to answer nearest neighbor queries, where one wants to find the object that is closest to a given query point. Nearest neighbor queries have numerous applications. For example, one might want to find the nearest hospital, or the most similar object in a database. A large application is vector quantization, commonly used in data compression.
With a given Voronoi diagram, one can also find the largest empty circle amongst a set of points, and in an enclosing polygon; e.g. to build a new supermarket as far as possible from all the existing ones, lying in a certain city.
The Voronoi diagram is useful in polymer physics. It can be used to represent free volume of the polymer.
It is also used in derivations of the capacity of a wireless network.
In climatology, Voronoi diagrams are used to calculate the rainfall of an area, based on a series of point measurements. In this usage, they are generally referred to as Thiessen polygons.
Voronoi diagrams are used to study the growth patterns of forests and forest canopies, and may also be helpful in developing predictive models for forest fires.
Voronoi diagrams are also used in computer graphics to procedurally generate some kinds of organic looking textures.
In autonomous robot navigation, Voronoi diagrams are used to find clear routes. If the points are obstacles, then the edges of the graph will be the routes furthest from obstacles (and theoretically any collisions).
In computational chemistry, Voronoi cells defined by the positions of the nuclei in a molecule are used to compute atomic charges. This is done using the Voronoi deformation density method.
Voronoi Polygons have been used in mining to estimate the reserves of valuable materials, minerals or other resources. Exploratory drillholes are used as the set of points in the Voronoi polygons.