Centroidal Voronoi tessellation
From Wikipedia, the free encyclopedia
In geometry, a centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation or Voronoi diagrams. A Voronoi tessellation is called centroidal when the generating point of each Voronoi cell is also its mean (center of mass). It can be viewed as an optimal partition corresponding to an optimal distribution of generators. A number of algorithms can be used to generate centroidal Voronoi tessellations, including Lloyd's algorithm and the K-means algorithm.
Gersho's conjecture, proven for 1 and 2 dimensions, says that "asymptotically speaking, all cells of the optimal CVT, while forming a tessellation, are congruent to a basic cell which depends on the dimension."[1]
Centroidal Voronoi tessellations are useful in data compression, optimal quadrature, optimal quantization, clustering, and optimal mesh generation.[2]
[edit] References
- ^ Du, Qiang; Wang, Desheng (2005), "The Optimal Centroidal Voronoi Tessellations and the Gersho's Conjecture in the Three-Dimensional Space", Computers and Mathematics with Applications (49): 1355-1373
- ^ Du, Qiang; Faber, Vance; Gunzburger, Max (1999), "Centroidal Voronoi Tesselations: Applications and Algorithms", SIAM Review 41 (4): 637–676, doi:10.1137/S0036144599352836.
