Lloyd's algorithm: Difference between revisions

Revision as of 22:49, 12 June 2011

Revision as of 15:41, 4 August 2011

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 slightly weaker convergence results are known {{harv|Sabin|1986}}, {{harv|Emelianenko|Ju|Rand|2009}}.

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 89:

| volume = 41

| year = 1999}}.

*{{citation

| last1 = Emelianenko | first1 = Maria

| last2 = Ju | first2 = Lili

| last3 = Rand | first3 = Alexander

| journal = SIAM Journal on Numerical Analysis

| pages = 1423–1441

| title = Nondegeneracy and Weak Global Convergence of the Lloyd Algorithm in $R^d$

| volume = 46

| year = 2009}}.

*{{citation

| last = Lloyd | first = Stuart P.