Lloyd's Algorithm

Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean space, partitioning those subsets into well shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest, with the nearest-centroid operation producing Voronoi diagrams. It can be used to construct close approximations to centroidal Voronoi tessellations, with applications including quantization, dithering, stippling, and the smoothing of triangle meshes in the finite element method.