In electrical engineering and computer science, 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 spaces and partitions of these subsets into well-shaped and uniformly sized convex cells.
Lloyd's algorithm can be used to construct close approximations to centroidal Voronoi tessellations of the input,[2] which can be used for quantization, dithering, and stippling.
Other applications of Lloyd's algorithm include smoothing of triangle meshes in the finite element method.
The algorithm was first proposed by Stuart P. Lloyd of Bell Labs in 1957 as a technique for pulse-code modulation.
Lloyd's algorithm starts by an initial placement of some number k of point sites in the input domain.
It then repeatedly executes the following relaxation step: Because Voronoi diagram construction algorithms can be highly non-trivial, especially for inputs of dimension higher than two, the steps of calculating this diagram and finding the exact centroids of its cells may be replaced by an approximation.
A common simplification is to employ a suitable discretization of space like a fine pixel-grid, e.g. the texture buffer in graphics hardware.
A cell's new center is approximated by averaging the positions of all pixels assigned with the same label.
Since a Voronoi cell is of convex shape and always encloses its site, there exist trivial decompositions into easy integratable simplices: Integration of a cell and computation of its centroid (center of mass) is now given as a weighted combination of its simplices' centroids (in the following called
Therefore, real-world applications of Lloyd's algorithm typically stop once the distribution is "good enough."
One common termination criterion is to stop when the maximum distance moved by any site in an iteration falls below a preset threshold.
[9] In the finite element method, an input domain with a complex geometry is partitioned into elements with simpler shapes; for instance, two-dimensional domains (either subsets of the Euclidean plane or surfaces in three dimensions) are often partitioned into triangles.
[11] In this application, despite varying the metric, Hausner continued to use centroids as the representative points of their Voronoi cells.
However, for metrics that differ more significantly from Euclidean, it may be appropriate to choose the minimizer of average squared distance as the representative point, in place of the centroid.