Scatter a handful of sites on a plane. For every other point in the plane, ask "which site is closest?" — the set of points that all share the same closest site forms that site's cell. Do this for every site and the plane splits into a mosaic of cells: a Voronoi diagram (also called a Thiessen tessellation). Formally, the cell of site P_k is R_k = { x : dist(x, P_k) ≤ dist(x, P_j) for all j }.

Under ordinary (Euclidean) distance, every cell boundary is dead straight: the edge between two neighboring sites' cells sits exactly on the perpendicular bisector of the segment joining them — every point on that line is equidistant from both sites. Where three or more bisectors meet at a single point, equidistant from three or more sites, that's a vertex. Because it's built from an intersection of half-planes, every cell is convex.

Connect two sites with a line whenever their cells share an edge, and you get the Delaunay triangulation — the mathematical "dual" of the Voronoi diagram. It has a famous defining property: no site ever falls inside another triangle's circumcircle. Toggle "Show Delaunay" in the panel to see it overlaid on the diagram below.

"Closest" depends on how you measure distance. This tool offers three: Euclidean (straight-line, √(Δx²+Δy²)) gives the straight-edged cells above; Manhattan (|Δx|+|Δy|, like walking city blocks) and Chebyshev (max(|Δx|,|Δy|), like a chess king's moves) both bend cell boundaries into diamonds and squares. Those two don't have straight-line bisectors, so this tool approximates them by sampling a fine grid and coloring each sample by its nearest site — the same idea as the GPU-friendly Jump Flooding Algorithm, just done here on the CPU.

Move every site to its own cell's centroid (center of mass), rebuild the diagram, and repeat. Cells that were too big push their site toward open space; cells that were too small get squeezed. Iterating this — Lloyd's algorithm — converges toward a centroidal Voronoi tessellation: evenly sized, evenly spaced cells, each site sitting at the center of its own territory. Hit "Relax" in the panel to watch it happen.

This tool clips each cell out of the canvas directly, testing every site against every other one — simple to follow, but O(n²) work. Real-world tools instead use Fortune's algorithm, a single left-to-right sweep that builds the whole diagram in O(n log n) time, or build the Delaunay triangulation incrementally (Bowyer–Watson, used for the overlay here) and take its dual. Neither is implemented as an animated sweep in this tool, to keep things focused on the geometry itself.

John Snow's 1854 map of a London cholera outbreak — cells around water pumps — is an early, famous use. Today the same idea underpins nearest-facility lookups (which store/hospital/cell-tower is closest), 1-nearest-neighbor classification in machine learning, and the boundary patterns of biological cells, mineral grains, and other tightly-packed natural structures.

Definitions, terminology and algorithm names from the Wikipedia Voronoi diagram article.