Interactive Voronoi tessellation with Lloyd's algorithm for centroidal Voronoi. Click to add seeds, watch relaxation to equal-area cells. Explore connections to optimal quantization and Delaunay triangulation.
Voronoi(S): V(p) = {x: d(x,p) ≤ d(x,q) ∀q∈S}. Dual = Delaunay triangulation. Lloyd's algorithm: centroidal Voronoi — iterate (1) compute Voronoi (2) move each seed to centroid of its cell. Converges to CVT minimizing quantization error E=Σ∫_{V_i}||x-s_i||²dx. Applications: k-means clustering, mesh generation, stippling (halftoning), radar coverage. CVT → hexagonal packing in 2D (asymptotically optimal).