Voronoi Diagram

A Voronoi diagram divides a plane into regions based on distance to a fixed set of points called seeds, so that every point inside a given region is closer to that region's own seed than to any other. It is named after the mathematician Georgy Voronoy, who formally defined and studied the general case in any number of dimensions in 1908, though the same construction had already appeared under other names, including the Dirichlet tessellation after Peter Gustav Lejeune Dirichlet and Thiessen polygons after the meteorologist Alfred Thiessen, who applied it to rainfall data in 1911. A Voronoi diagram is mathematically dual to the Delaunay triangulation of the same point set. An early informal use of the idea is credited to Descartes in 1644, and John Snow's 1854 map of cholera cases around a single water pump in London is often cited as an early practical use of the same kind of proximity region.