Lloyd's algorithm: Difference between revisions

Revision as of 17:00, 7 June 2013

Revision as of 15:01, 12 June 2013

Line 41:

* Each point is then moved to the centroid of its Voronoi cell.

Obtaining the Voronoi cells and computing its centroid analytically is not a trivial task, and [[Monte Carlo methods]] isare typically used for this purpose. In this method, random sample points are generated according to some fixed underlying probability distribution. These sample points are also known as training samples. In practice, the underlying probability distribution is often unknown and the training samples are obtained from raw field data. Each training sample is declared to belong to the Voronoi cell corresponding to the nearest seed point to it. The average of the training samples collected in each Voronoi cell gives the new centroids of 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}}.