Centroidal Voronoi tessellation — iterative energy minimization
Click canvas to add seeds, or generate random
Lloyd's algorithm iteratively moves each seed to the centroid of its Voronoi cell. Starting from any configuration, this converges to a centroidal Voronoi tessellation (CVT) where every generator equals its cell's centroid — a fixed point of the map. CVTs minimize the energy E = Σᵢ ∫_{Vᵢ} ‖x−cᵢ‖² ρ(x)dx (sum of weighted squared distances from centroid). They appear in optimal quantization, mesh generation, cellular biology (Giraffe spots!), and materials science (foam structure). Fortune's algorithm gives the exact Voronoi; here we use a scanline rasterization for centroids.