a Voronoi diagram

Scatter a few post offices across a city. For any address, which post office is nearest? If you color every point of the map by its closest post office, the city splits into regions — one territory per office, each containing exactly the places for which that office is the nearest. The map of these territories is a Voronoi diagram. It is the natural way to carve space into 'spheres of influence' around a set of sites.

Precisely, start with a finite set of points called sites, P_1, P_2, ..., P_n. The Voronoi cell of site P_i is the set of all points in the plane that are closer to P_i than to any other site. These cells partition the whole plane (ties forming the boundaries). The boundary between two neighboring cells lies on the perpendicular bisector of the segment joining their two sites — the line of points exactly equidistant from both — which is why every cell is a convex polygon, bounded by straight edges. Where three cells meet, at a Voronoi vertex, the point is equidistant from three sites at once, so it is the center of a circle passing through all three. Building the diagram for n sites in the plane takes time proportional to n log n, achieved elegantly by Fortune's sweepline algorithm.

Voronoi diagrams are everywhere once you look: they model how crystals grow, where rainwater drains, which cell tower your phone connects to, and how ecologists partition territory; they answer nearest-neighbor queries, drive mesh generation, and appear in art and architecture. They are named for Georgy Voronoi but were used earlier by Dirichlet and even by John Snow, who in 1854 mapped cholera deaths around water pumps. One honest caveat: the diagram depends entirely on the chosen distance. The familiar straight-line (Euclidean) version gives polygonal cells, but switch to a different metric — city-block distance, say, or distances weighted by site importance — and the cell shapes change completely, sometimes with curved or even disconnected boundaries.