Centroidal Voronoi tessellation: Difference between revisions
m sp |
added a bit about weighted CVT and an example of its use |
||
| Line 3: | Line 3: | ||
Gersho's conjecture, proven for one and two dimensions, says that "asymptotically speaking, all cells of the optimal CVT, while forming a tessellation, are [[Congruence_(geometry)|congruent]] to a basic cell which depends on the dimension."<ref>{{citation|first1=Qiang|last1=Du|first2=Desheng|last2=Wang|title=The Optimal Centroidal Voronoi Tessellations and the Gersho's Conjecture in the Three-Dimensional Space|journal=Computers and Mathematics with Applications|issue=49|year=2005|pages=1355–1373}}</ref> In two dimensions, the basic cell for the optimal CVT is a regular [[hexagon]]. |
Gersho's conjecture, proven for one and two dimensions, says that "asymptotically speaking, all cells of the optimal CVT, while forming a tessellation, are [[Congruence_(geometry)|congruent]] to a basic cell which depends on the dimension."<ref>{{citation|first1=Qiang|last1=Du|first2=Desheng|last2=Wang|title=The Optimal Centroidal Voronoi Tessellations and the Gersho's Conjecture in the Three-Dimensional Space|journal=Computers and Mathematics with Applications|issue=49|year=2005|pages=1355–1373}}</ref> In two dimensions, the basic cell for the optimal CVT is a regular [[hexagon]]. |
||
Centroidal Voronoi tessellations are useful in [[data compression]], optimal [[Numerical integration|quadrature]], optimal [[Quantization (signal processing)|quantization]], [[Data clustering|clustering]], and optimal mesh generation.<ref name="Du_2">{{citation|first1=Qiang|last1=Du|first2=Vance|last2=Faber|author2-link=Vance Faber|first3=Max|last3=Gunzburger|title=Centroidal Voronoi Tessellations: Applications and Algorithms|doi=10.1137/S0036144599352836|journal=SIAM Review|volume=41|issue=4|pages=637–676|year=1999}}.</ref> Many [[patterns in nature|patterns seen in nature]] are closely approximated by a Centroidal Voronoi tessellation. Examples of this include the [[Giant's Causeway]], the cells of the [[cornea]], <ref>PIGATTO, João Antonio Tadeu et al. Scanning electron microscopy of the corneal endothelium of ostrich. ''Cienc. Rural'' [online]. 2009, vol.39, n.3 [cited 2011-06-11], pp. 926-929 . Available from: <http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-84782009000300047&lng=en&nrm=iso>. Epub Jan 09, 2009. ISSN 0103-8478. {{doi|10.1590/S0103-84782009005000001}}</ref> and the breeding pits of the male [[tilapia]]. <ref name=Du_2/> |
Centroidal Voronoi tessellations are useful in [[data compression]], optimal [[Numerical integration|quadrature]], optimal [[Quantization (signal processing)|quantization]], [[Data clustering|clustering]], and optimal mesh generation.<ref name="Du_2">{{citation|first1=Qiang|last1=Du|first2=Vance|last2=Faber|author2-link=Vance Faber|first3=Max|last3=Gunzburger|title=Centroidal Voronoi Tessellations: Applications and Algorithms|doi=10.1137/S0036144599352836|journal=SIAM Review|volume=41|issue=4|pages=637–676|year=1999}}.</ref> Many [[patterns in nature|patterns seen in nature]] are closely approximated by a Centroidal Voronoi tessellation. Examples of this include the [[Giant's Causeway]], the cells of the [[cornea]], <ref>PIGATTO, João Antonio Tadeu et al. Scanning electron microscopy of the corneal endothelium of ostrich. ''Cienc. Rural'' [online]. 2009, vol.39, n.3 [cited 2011-06-11], pp. 926-929 . Available from: <http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-84782009000300047&lng=en&nrm=iso>. Epub Jan 09, 2009. ISSN 0103-8478. {{doi|10.1590/S0103-84782009005000001}}</ref> and the breeding pits of the male [[tilapia]]. <ref name=Du_2/> |
||
A weighted centroidal Voronoi diagrams is a CVT in which each centroid is weighted according to a certain function. For example, a [[grayscale]] image can be used as a density function to weight the points of a CVT, as a way to create digital [[stippling]].<ref>Secord, Adrian. "Weighted voronoi stippling." Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering. ACM, 2002.</ref> |
|||
{{multiple image |
{{multiple image |
||
Revision as of 23:19, 6 August 2014
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 for K-means clustering.
Gersho's conjecture, proven for one and two 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] In two dimensions, the basic cell for the optimal CVT is a regular hexagon.
Centroidal Voronoi tessellations are useful in data compression, optimal quadrature, optimal quantization, clustering, and optimal mesh generation.[2] Many patterns seen in nature are closely approximated by a Centroidal Voronoi tessellation. Examples of this include the Giant's Causeway, the cells of the cornea, [3] and the breeding pits of the male tilapia. [2]
A weighted centroidal Voronoi diagrams is a CVT in which each centroid is weighted according to a certain function. For example, a grayscale image can be used as a density function to weight the points of a CVT, as a way to create digital stippling.[4]
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
- ^ a b Du, Qiang; Faber, Vance; Gunzburger, Max (1999), "Centroidal Voronoi Tessellations: Applications and Algorithms", SIAM Review, 41 (4): 637–676, doi:10.1137/S0036144599352836.
- ^ PIGATTO, João Antonio Tadeu et al. Scanning electron microscopy of the corneal endothelium of ostrich. Cienc. Rural [online]. 2009, vol.39, n.3 [cited 2011-06-11], pp. 926-929 . Available from: <http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-84782009000300047&lng=en&nrm=iso>. Epub Jan 09, 2009. ISSN 0103-8478. doi:10.1590/S0103-84782009005000001
- ^ Secord, Adrian. "Weighted voronoi stippling." Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering. ACM, 2002.