a Voronoi diagram
/ vuh-roh-NOY /
Scatter a handful of fire stations across a city and ask: for each point in the city, which station is nearest? The map of answers carves the city into regions, one per station, each region being the territory closest to its station. That partition is the Voronoi diagram. It is one of the most natural structures in all of geometry — nature uses it for everything from cell shapes to crystal grains to giraffe spots.
Formally, given a set of sites P = {p_1, ..., p_n} in the plane (or R^d) with a distance, the Voronoi cell of p_i is the set of all points strictly closer to p_i than to any other site: V(p_i) = { x : d(x, p_i) <= d(x, p_j) for all j }. These cells are convex polygons (in the Euclidean plane) that tile the whole space; their shared boundaries are the perpendicular bisectors between neighboring sites — every point on the edge between two cells is equidistant from their two sites. The vertices of the diagram are points equidistant from three or more sites, the centers of empty circles through those sites. The diagram is the exact geometric dual of the Delaunay triangulation: connect two sites whose cells touch and you get the Delaunay edges. It can be computed in O(n log n) by Fortune's sweepline or via the lifted-paraboloid convex hull.
Voronoi diagrams are everywhere applied: nearest-neighbor queries, facility location, motion planning (stay on the edges to keep maximally far from obstacles), natural-neighbor interpolation, mesh generation, and modeling growth in biology and materials. The duality with Delaunay means each structure can be read off the other, a recurring theme in computational geometry. Honest caveats: cells of sites on the outer boundary (the convex hull) are unbounded, extending to infinity, which robust implementations must handle specially; the diagram changes discontinuously as sites move past cocircular configurations; and 'Voronoi' presupposes a distance — with a different metric (Manhattan, or a weighted/power distance) the cells need not be convex polygons and the clean Delaunay duality is modified.
With just two sites, the Voronoi diagram is a single line: the perpendicular bisector of the segment joining them, splitting the plane into two half-planes (everyone on the left is closer to the left site). Add a third site and the three pairwise bisectors meet at one point — the circumcenter of the triangle, equidistant from all three — which is a Voronoi vertex and the dual of the single Delaunay triangle.
Voronoi edges are perpendicular bisectors; a vertex is a circumcenter equidistant from three sites.
Voronoi and Delaunay are duals but not interchangeable as data: cells of convex-hull sites are unbounded and need special handling, and the whole construction presupposes a metric. Under a non-Euclidean distance (e.g. power/weighted Voronoi) cells may stop being convex polygons and the tidy Delaunay duality is altered.