Content deleted Content added
computing voronoi cells and the centroid |
No edit summary |
||
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]] is typically used for this purpose. In this method, random sample points are generated according to some fixed probability distribution. Each random point is declared to belong to the Voronoi cell corresponding to the nearest seed point to it. After a large number of random samples have been generated, the average of random 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}}.
| |||