Lloyd's algorithm: Difference between revisions

Revision as of 18:11, 5 November 2007

Revision as of 06:02, 27 December 2007

Line 7:

* 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 twohigher dimensions, itsome isweaker conjecturedconvergence toresults convergeare butknown no(Sabin, proof1986). yet exists.

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.

Line 21:

* 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.