Voronoi Tessellations

The use of Voronoi diagrams can be traced back to 1644 and Rene Descartes. Voronoi diagrams were used by Lejeune Dirichlet in a 1850 study of quadratic forms. John Snow (British physician) illustrated in 1854 that the majority of people who died of cholera in the Soho area of London lived closer to a particularly infected well, located on Broad Street, than to any other water pump by using Voronoi analysis.

Voronoi diagrams are used in meterology and geophysics to analyze spatial distributions of rainfall and resources. They find contemporary use in city planning and marketing where a "best" route to a city hospital, or best location (relative to the nearest competition) of a store can be mathematically determined.

Named after Georgy Voronoi, a Voronoi tesselation is a plane of S points (Voronoi sites) where each point s is in a cell V(s) that consists of all points closer to s than to any other site. A Voronoi node is comprised of all the points that are equidistant to three (or more) sites.

// The Voronoi diagram shown is a set of random points in a plane //

In general, the set of all points closer to a point c of S than to any other point of S is the interior of a (in some cases unbounded) convex polytope called a Voronoi cell for c. The set of such polytopes is the Voronoi tessellation corresponding to the set S. When the dimension of the space is 2 the Voronoi tessellation can be easily drawn (as shown) and are sometimes referred to as Voronoi diagrams. When the space is 3 or higher the tesellations are complex and difficult to envison. Want to know more? Ask, or visit Wikipedia or Wolfram's MathWorld.