Voronoi Diagrams

The Voronoi diagram (also called a Dirichlet tessellation or a set of Thiessen polygons) is a partition of a metric space such that we associate all locations in that space with the closest object in that space, based on the specified metric. Thus, each object is the generator of a cell or tile, and the set of tiles covers the space or map.

In the simplest case, we are given a set of points S in the Euclidean plane, which are the Voronoi generators. Each generator, s, has a Voronoi cell, V(s), consisting of all points closer to s than to any other generator. The cell boundaries of the Voronoi diagram are all the points in the plane that are equidistant to two generators, and the Voronoi nodes are the points equidistant to three (or more) generators. Voronoi cells can be defined for metrics other than Euclidean, such as the Manhattan distance, and for other surfaces than the plane, such as the sphere. Voronoi cells can also be defined by measuring distances to objects that are not points. The dual graph of the Voronoi diagram of S corresponds to the Delaunay triangulation (DT) of S (Figure 1). Here, all Voronoi cells have generators that form the vertices of the DT, all Voronoi edges have perpendicular Delaunay edges, and all Voronoi vertices are the centers of the circumcircles of the DT.

Figure 1 The Voronoi diagram of a set of points, together with the dual Delaunay triangulation

Source: Author.

The idea of the Voronoi diagram is relevant in many spatial sciences, giving descriptions of proximity, adjacency, clustering, territoriality, and others. The DT is widely used as a stable and well-defined triangulation for terrain modeling. Informal use of Voronoi diagrams can be traced back to Descartes in 1644. The Voronoi diagram was used in 1854 by the British physician John Snow to show that the majority of people who died during the cholera epidemic in the Soho district of London lived closer to the contaminated pump at Broad Street than to any other source of water.