For faster navigation, this Iframe is preloading the Wikiwand page for Centroidal Voronoi tessellation.

Centroidal Voronoi tessellation

From Wikipedia, the free encyclopedia

Three centroidal Voronoi tessellations of five points in a square

In geometry, a centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation in which the generating point of each Voronoi cell is also its centroid (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 or Quasi-Newton methods like BFGS. [1]

Proofs

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."[2]

In two dimensions, the basic cell for the optimal CVT is a regular hexagon as it is proven to be the most dense packing of circles in 2D Euclidean space. Its three dimensional equivalent is the rhombic dodecahedral honeycomb, derived from the most dense packing of spheres in 3D Euclidean space.

Applications

Centroidal Voronoi tessellations are useful in data compression, optimal quadrature, optimal quantization, clustering, and optimal mesh generation.[3]

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]

Occurrence in nature

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,[5] and the breeding pits of the male tilapia.[3]


References

  1. ^ Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization. Springer Series in Operations Research and Financial Engineering (second ed.). Springer. doi:10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1.
  2. ^ 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 (9–10): 1355–1373, doi:10.1016/j.camwa.2004.12.008
  3. ^ a b Du, Qiang; Faber, Vance; Gunzburger, Max (1999), "Centroidal Voronoi Tessellations: Applications and Algorithms", SIAM Review, 41 (4): 637–676, Bibcode:1999SIAMR..41..637D, CiteSeerX 10.1.1.452.2448, doi:10.1137/S0036144599352836.
  4. ^ Secord, Adrian. "Weighted voronoi stippling." Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering. ACM, 2002.
  5. ^ Pigatto, João Antonio Tadeu; et al. (2009). "Scanning electron microscopy of the corneal endothelium of ostrich". Cienc. Rural. 39 (3): 926–929. doi:10.1590/S0103-84782009005000001.
{{bottomLinkPreText}} {{bottomLinkText}}
Centroidal Voronoi tessellation
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.