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 after Georgy Voronoi, a mathematician born in Ukraine in 1868. He is remembered today mostly for this diagram, also known as a Voronoi tessellation, decomposition or partition.
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.
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.
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 accompanying figure). Proximity diagrams were used by many mathematicians, back to Descartes in the mid-17th 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, with n being the number of dimensions.
Biological structures
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.
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 applications 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 tessellating a region in terms of distance to a given set of points can be so powerful.
Peter Lynch is emeritus professor at the school of mathematics and statistics, University College Dublin. He blogs at thatsmaths.com