Lloyd's algorithm: Difference between revisions

Revision as of 15:01, 30 May 2010

Revision as of 15:03, 30 May 2010

Line 41:

* 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]] ({{harv|Du, |Emelianenko|Ju|2006)}}. In higher dimensions, some weaker convergence results are known ({{harv|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.

Line 47:

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]] ({{harv|Deussen,|Hiller|van Overveld|Strothotte|2000)}}. In this application, the centroids can be weighted based on a reference image ({{harv|Secord, |2002)}} to produce stipple illustrations matching an input image.

== See also ==