We frequently need to find the nearest hospital, surgery or supermarket. A map divided into cells, each cell covering the region closest to a particular centre, can assist us in our quest. Such a map is called a Voronoi diagram, named for Georgy Voronoi, a mathematician born in Ukraine in 1868. He is remembered today mostly for his diagram, also known as a Voronoi tessellation, decomposition, or partition. [TM108 or search for “thatsmaths” at irishtimes.com].
Voronoi diagram drawn using the applet of Paul Chew (see Sources below).
Another practical problem is to choose a location for a new service, such as a school, which is as far as possible from existing schools while still serving the maximum number of families. A Voronoi diagram can be used to find the largest empty circle amid a collection of points, giving the ideal location for the new school. Of course, numerous parameters other than distance must be considered, but access time is often the critical factor.
Georgy Fedosevich Voronoi (1868-1908)
In mathematical terms, we are given a finite set of points in the plane and, for each point, the corresponding Voronoi cell consists of all the locations closer to it than to any of the other points. The cells are all convex polygons; that is, they have boundaries made up of straight line segments and all corners have internal angles less than 180 degrees.
Construction of Voronoi Diagrams
Voronoi diagrams are easily constructed and, with computer software, can be depicted as colourful charts, indicating the region associated with each service-point or site. For any location, the nearest service can immediately be read off the diagram (see the figure above). Voronoi diagrams were used by many mathematicians, back to Descartes in the mid-seventeenth century, but their theory was developed by Voronoi, who in 1908 defined and studied diagrams of this type in the general context of n-dimensional space.
Voronoi diagrams have applications in almost all areas of science and engineering. Biological structures can be described using them. In aviation, they are used to identify the nearest airport in case of diversions. In mining, they can aid estimation of overall mineral resources based on exploratory drill-holes. In epidemiology, they can help in identifying the source of infections.
John Snow and the Cause of Cholera
One of the first applications of a Voronoi diagram was by Dr John Snow, a prominent London physician. Cholera, which became widespread in the 19th century, has killed tens of millions of people. Before the cholera bacterium was isolated, overcrowding, bad diet, poor sanitation and noxious miasma emanating from rotting organic matter were all suspected. Snow believed that cholera was caused by infected drinking water.
A serious cholera outbreak in 1854 killed 500 people in five days. Snow gathered statistics on the number of victims and locations of outbreaks. He divided inner London into neighbourhoods, each having a separate water supply. He plotted his data on a chart, effectively constructing a Voronoi diagram. This revealed that almost all fatalities were in houses supplied by a single pump in Broad Street, Soho. When the pump handle was removed, death rates were greatly diminished and the epidemic quickly died out. An engineering survey later showed that a poorly constructed drain was contaminating the pump water.
There are numerous other application of Voronoi diagrams. These include network analysis, computer graphics, medical diagnostics, astrophysics, hydrology, robotics and computational fluid dynamics. It is surprising how the simple concept of partitioning a region in terms of distance to a given set of points can be so powerful.
Sources
Interactive Voronoi Diagram Generator of Alex Beutel: WebGL
Applet and Source code to generate Voronoi diagrams (Author: Paul Chew, chew@cs.cornell.edu).
* * *
The collection 
That’s Maths, with 100 articles, has just been published by Gill Books. Available from
ThatsMaths 