Lloyd's algorithm: Difference between revisions

Revision as of 18:46, 3 November 2007

Revision as of 18:11, 5 November 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 [[Voronoi diagram#Centroidal_Voronoi_tessellations|centroidal Voronoi tessellation]] (Du, 2006). In two dimensions, it is conjectured to converge but no proof 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.