Lloyd's algorithm

In computer graphics and electrical engineering, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is a method for evenly distributing samples or objects, usually points.

Lloyd's algorithm starts with an initial distribution of samples or points and consists of repeatedly executing one relaxation step:

* The Voronoi diagram of all the points is computed.
* Each cell of the Voronoi diagram is integrated and the centroid is computed.
* Each point is then moved to the centroid of its voronoi cell.

Each time a relaxation step is performed, the points are left in a slightly more even distribution: closely spaced points move further apart, and widely spaced points move closer together. In one dimension, this algorithm has been shown to converge to a centroidal Voronoi diagram, also named a centroidal Voronoi tessellation (Du, 2006). In higher dimensions, some weaker convergence results are known (Sabin, 1986).

Since the algorithm converges slowly, and, due to limitations in numerical precision the algorithm will often not converge, real-world applications of Lloyd's algorithm stop once the distribution is "good enough." One common termination criterion is when the maximum distance a point moves in one iteration is below some set limit.

Lloyd's method is used in computer graphics because the resulting distribution has blue noise characteristics (see also Colors of noise), meaning there are few low-frequency components that could be interpreted as artifacts. It is particularly well-suited to picking sample positions for dithering.

Lloyd's algorithm is also used to generate dot drawings in the style of stippling (Deussen, 2000). In this application, the centroids can be weighted based on a reference image (Secord, 2002) to produce stipple illustrations matching an input image.

See also

* The Linde-Buzo-Gray algorithm, which is a generalization of this algorithm.

References

* Oliver Deussen, Stefan Hiller, Cornelius van Overveld, and Thomas Strothotte. "Floating Points: A Method for Computing Stipple Drawings." Computer Graphics Forum, vol. 19, no. 3, (Proceedings of Eurographics), pp. 41-51, 2000.
* Qiang Du, Maria Emelianenko, and Lili Ju. "Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations." SIAM Journal of Numerical Analysis, vol. 44, pp. 102-119, 2006.
* Qiang Du, Vance Faber, and Max Gunzburger. "Centroidal Voronoi Tessellations: Applications and Algorithms." Siam Review, vol. 41, no. 4, pp. 637-676, 1999.
* Stuart P. Lloyd. "Least Squares Quantization in PCM." IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129-137, 1982.
* J. Sabin and R. Gray. "Global Convergence and Empirical Consistency of the Generalized Lloyd Algorithm." IEEE Transactions on Information Theory , vol. 32, no. 2, pp. 148-155, 1986.
* Adrian Secord. "Weighted Voronoi Stippling." Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (NPAR), pp. 37-43, 2002.