Geometric Tessellations and Triangulations
A Voronoi diagram partitions a plane into regions based on distance to seed points. Each cell contains all points closer to its seed than to any other seed. Named after Georgy Voronoi, these diagrams appear everywhere in nature - from cell structures to territorial boundaries.
The Delaunay triangulation maximizes the minimum angle of all triangles, avoiding sliver triangles. It's the dual graph of the Voronoi diagram - each Voronoi edge corresponds to a Delaunay edge connecting the adjacent seed points. Used extensively in mesh generation, terrain modeling, and finite element analysis.
Lloyd's algorithm iteratively moves each point to the centroid of its Voronoi cell, creating a more uniform distribution. After many iterations, points converge to a centroidal Voronoi tessellation (CVT) - widely used in image stippling, mesh generation, and optimal facility placement.
The Voronoi diagram and Delaunay triangulation are mathematical duals. Each Voronoi vertex is the circumcenter of a Delaunay triangle, and Voronoi edges are perpendicular bisectors of Delaunay edges. This duality is fundamental in computational geometry.