Voronoi / Delaunay
Drop n points on a plane. For each point, the Voronoi cell is the region closer to it than to any other. Cell boundaries form a tiling. The dual structure — connect points whose cells share an edge — is the Delaunay triangulation, used in everything from finite-element meshes to k-nearest-neighbor algorithms to crystal lattice analysis.
why these two structures are the same structure
The Voronoi diagram and Delaunay triangulation are duals: each is reconstructible from the other.
Voronoi cell of point i: {x ∈ ℝ² : ‖x − p_i‖ ≤ ‖x − p_j‖ for all j ≠ i}. This is the set of locations closer to p_i than to any other point.
Delaunay triangulation: connect three points p_i, p_j, p_k into a triangle iff their circumscribed circle contains no other point of the input. Equivalently: the triangulation that maximizes the minimum interior angle — avoiding skinny triangles.
Duality:
• Each Delaunay triangle's circumcenter = a Voronoi vertex.
• Each Delaunay edge crosses one Voronoi edge perpendicularly.
• Each Delaunay vertex corresponds to one Voronoi cell.
Lloyd's relaxation: repeat "compute Voronoi cells, move each point to its cell's centroid". The result converges toward a centroidal Voronoi tessellation — cells of roughly equal size and Lloyd's algorithm is foundational to:
• Mesh generation for finite element methods
• Image stippling (Adrian Secord's art technique)
• Wireless network base station placement
• Cellular biology — animal coat patterns sometimes emerge from Voronoi-like cell competition
Where Voronoi/Delaunay appears in nature:
• Bee honeycomb: regular hexagonal Voronoi tessellation, optimal under area-minimization (Hales 1999)
• Giraffe spots, leopard rosettes: roughly Voronoi-like in spacing
• Geological column joints (Giant's Causeway, Devil's Postpile): cooling basalt fractures into Voronoi-style hexagonal columns
• Crystallography: Brillouin zones in solid-state physics are Voronoi cells in reciprocal space
• Galaxy distributions: voids and walls form approximate Voronoi structure