×
About Nearest Pump
Every spot on the map belongs to the pump nearest to it. Shade each pump's share and the map breaks into regions with straight edges: a Voronoi diagram . The edge between two regions is the line exactly half-way between their pumps, and where three regions meet is a spot the same distance from three pumps.
MAP : click the paper to add a pump, drag one to move it, pick one and press DELETE (or the Delete key, or right-click it) to take it away. With a pump picked, the arrow keys nudge it (Shift for small steps) and [ ] pick the previous or next one. Change how distance is measured: straight line , city blocks (only along east–west and north–south, as in a grid of streets) or chessboard (a king's moves: a diagonal step costs the same as a straight one). Bigger pumps draw from further away: with ADDED each size step takes 60 m off that pump's distance (the edges bend into hyperbolas); with MULTIPLIED its distance is divided by 1, 1.5, 2, 2.5 or 3 (the edges become circles, and a big pump can surround a small one completely). Delaunay triangles join pumps whose regions touch; Empty circles draws the circle through each triangle's corners (point at one to pick it out). Furthest spot marks the place furthest from every pump, the best spot for a new one, and PUT A PUMP THERE does just that.
BROAD STREET retells John Snow's cholera map of 1854 on a simplified plan of the streets: regions by straight line or by walking along the streets, the shortest walk from any house you click, and the pump handle taken off.
NATURE grows patterns from scattered points. RELAX moves every point to the middle of its own region and redraws; repeat it and the regions even out.
THE STORY
The idea is old. René Descartes drew space divided into regions round the stars in 1644. Peter Gustav Lejeune Dirichlet used it for quadratic forms in 1850, and Georgy Voronoy studied it in any number of dimensions in 1908, so the regions are called Dirichlet or Voronoi cells. In 1911 the American meteorologist Alfred Thiessen used them to share out rainfall between rain gauges (Thiessen polygons), and Boris Delaunay, building on Voronoy's work, described the triangles in 1934.
In August and September 1854 cholera killed about 616 people in a few streets of Soho in London, most of them in the first days of September. The physician John Snow believed cholera was spread by dirty water, not by bad air as most people thought. He found that the dead had mostly drawn their water from the public pump in Broad Street, and on 7 September he put his case to the Board of Guardians of St James's parish. The pump handle was taken off the next day, 8 September. Snow himself said the outbreak was already falling by then, as many people had fled.
His map of the deaths, a black bar for each death outside each house, was published in the 1855 second edition of his book On the Mode of Communication of Cholera . A second version, drawn for the parish's Cholera Inquiry Committee report the same year, added a dotted line: the "boundary of equal distance" between the Broad Street pump and the other pumps, measured by the shortest way along the streets, not as the crow flies. It is in effect a Voronoi diagram by walking distance, and the deaths fall almost entirely inside it. Snow pointed out the exceptions too: a workhouse on Poland Street with its own well, where only five of over 500 inmates died, and the brewery in Broad Street, where none of the 70 or so workmen died; they drank beer, and the brewery had its own well. A widow in Hampstead, miles away, died after having the water brought to her because she liked its taste. The local curate, Henry Whitehead, later traced how the well was probably contaminated: a baby at 40 Broad Street had fallen ill just before the outbreak, and its nappies were rinsed into a cesspool a few feet from the well.
Lloyd's relaxation comes from Stuart Lloyd's work at Bell Labs on turning signals into a few levels (1957, published 1982). Michael Shamos and Dan Hoey brought Voronoi diagrams into computer science in 1975, including the largest empty circle.
HOW IT WORKS
Straight line : each pump's region is what is left of the map after cutting it along the half-way line to every other pump and keeping this pump's side. Every region is a convex polygon. Pumps further away than twice the region's reach can't cut it any more, so the cutting stops early. Two pumps on the same spot share one region; pumps in a row get strips; four pumps on one circle meet at a single corner. The answer is exact, not drawn pixel by pixel.
Delaunay triangles come from the corners: where three regions meet is the centre of a circle through those three pumps with no pump inside it (the empty circle ), and those three make a triangle. Where four or more meet (a square grid of pumps), any way of splitting them into triangles is equally good.
City blocks, chessboard and bigger pumps don't give straight half-way lines everywhere, so the page asks "which pump wins?" at a fine grid of spots, then finds the exact spot where two pumps tie along each grid line between spots that disagree, and joins them into the boundaries. Region shares in the field book come from the grid, so they are close rather than exact.
The furthest spot , by straight line, is always at a corner of a region (a Voronoi corner, where an edge meets the map's edge, or a map corner), so checking every corner finds it exactly. For the other distances the page searches a grid and then climbs towards the best spot in ever smaller steps. Its "circle" is a diamond for city blocks and a square for the chessboard, as those are the shapes of all spots one distance away.
Walking : the streets are a network of junctions and street pieces. From each pump the page finds the shortest walk to every junction (Dijkstra's method); the walk to a house is the shortest way to either end of its piece of street, then along it. Each spot off the streets is shaded by the pump nearest once you step onto the closest street.
Relaxing (Lloyd's method): move each point to the centre of its own region, the balance point of the polygon, and redraw. Each step makes the total spread of every region around its point smaller, the regions grow more even and more of them have six sides. Inside a big map the regions always average about six sides, because of Euler's formula for networks. The giraffe, mud and cell pictures are looks, not models: giraffe patches, mud cracks and plant cells only resemble Voronoi patterns. Plant cells are made by stretching the map before working out the regions.
The Broad Street plan is made up for this page: the streets are named after the real ones but straightened and spaced to fit, the pumps are only roughly where Snow's map shows pumps (A is the Broad Street pump; the other names are just the nearest street on this plan), and the deaths are generated to cluster round the Broad Street pump by walking distance, the pattern his map shows. It is not his data.
FURTHER WATCHING AND READING