Iterative scheme that relocates a set of generating points by repeatedly replacing each point with the centroid of its Voronoi cell, producing centroidal Voronoi tessellations in the limit and reducing a quantization energy measuring average squared distance to generators.

Principle

Lloyd iteration is gradient-descent-like on the quantization (CVT) energy: moving each generator to the mass centroid of its Voronoi region decreases the L^2 quantization functional, promotes uniform spacing in convex domains, and converges under regularity assumptions to a (local) centroidal configuration.

Demonstration

Start with random points in a unit square, compute the Voronoi partition, replace each point by its cell centroid, and iterate; after many steps the points approximate a hexagonal lattice pattern in the interior and sample the domain quasi-uniformly. On a curved surface, centroids are computed with respect to surface area measure and updates must be projected back to the surface.

Misapplication

Running Lloyd without enforcing domain constraints or feature projection can move points out of admissible region; using Lloyd as a one-size-fits-all optimizer ignores that it only decreases L^2 energy and may converge slowly, get stuck in local minima, or destroy boundary sampling patterns if centroids are computed naively.

Consequence

Properly applied, Lloyd's algorithm produces well-spaced sampling points, improves mesh quality for centroidal-based remeshing, and reduces quantization error; however it may require many iterations, careful handling of boundaries and obstacles, and seeding strategies to avoid poor local minima.

Reversal

The inverse process (recapturing previous generator positions from centroids) is not uniquely defined because information is lost by averaging; maximizing the quantization functional (pushing points to cluster) yields opposite, nonuniform distributions and is unstable under the same updates.

Boundary

Applies to domains where Voronoi cells and centroids are well-defined under a chosen measure (Euclidean area, surface area, or weighted density); excluded are cases with singular measures, disconnected admissible sets without projection, or constraints forbidding centroid relocation (hard obstacles, fixed feature points).

Semantic Tension

Relate Lloyd's algorithm to k-means clustering: mathematically identical to batch k-means in continuous settings for L^2 loss, but Lloyd is used for geometric sampling and CVT construction while k-means targets data clustering; Lloyd targets centroidal regularity not necessarily perceptual clustering.

Synthesis

Lloyd's algorithm is the simple, local-to-global iterative procedure that reduces L^2 quantization energy by moving generators to Voronoi centroids: compute Voronoi cells, replace points by centroids (with projection and density weighting as needed), and iterate until a centroidal Voronoi tessellation or satisfactory sampling is obtained.