Which Shop Is Nearest? Draw That for Every Point at Once

Start with a scatter of points on a plane. For each point, collect every location that is closer to it than to any other point in the set, and that collection is its region. The regions tile the plane completely with no gaps and no overlaps. The boundary between two neighbouring regions is the set of locations equidistant from both, which is the perpendicular bisector of the line joining them, so every region is bounded by straight edges and is convex. Where three regions meet, the corner is equidistant from three points at once.

Several useful facts drop straight out of the construction:

• •Every region is a convex polygon, possibly unbounded at the edge
• •A region has an edge with another only if those two points are neighbours
• •Corners are centres of circles passing through three points with none inside
• •Joining every neighbouring pair produces a companion triangulation
• •That triangulation avoids thin slivers, which matters in modelling
• •The whole structure can be built in time close to the number of points

The construction is named after Georgy Voronoy, who formalised it in 1908, and the idea was used decisively half a century earlier. In 1854 John Snow investigated a cholera outbreak in Soho in London and drew on his map the area within which the Broad Street pump was the nearest source of water, which is exactly one such region. Deaths clustered inside that boundary and dropped away sharply outside it, and the apparent exceptions turned out on investigation to be people who preferred that pump's water or who drank it at work. The line made the argument visible in a way a list of addresses could not.

The basic construction assumes straight-line distance on a flat plane, and changing any of those assumptions changes the picture usefully. Measuring distance along a street network instead produces regions with ragged boundaries that follow the roads, which is what a delivery zone actually looks like. Giving the points different weights, so that a larger facility draws from further away, curves the boundaries into arcs rather than straight lines. Working on a sphere rather than a plane matters at continental scale. And the construction extends to three dimensions, where it is used to model packing, foams and the arrangement of atoms.

Anything that grows outwards at an equal rate from scattered starting points ends up dividing space this way, which is why the pattern is common in nature rather than merely useful in mathematics. Crystal grains in cooled metal meet along such boundaries, since each grain grows from a nucleus until it meets its neighbours. The markings on a giraffe approximate it. So do the cells in some leaf and wing tissues, and the territories of some ground-nesting birds. In practical use it underlies nearest-facility planning for hospitals and schools, mobile network cell coverage, and interpolation from scattered weather stations.

Assigning every location to its nearest point in a scatter divides the plane into convex regions bounded by perpendicular bisectors, with no gaps or overlaps. John Snow drew one in 1854 to show cholera deaths clustering around a single pump. Anything growing outwards at equal speed from scattered seeds produces the pattern, which is why metal grains and giraffe markings share it.