Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Centroidal Voronoi tessellation
Résumé
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.
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."
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.
Centroidal Voronoi tessellations are useful in data compression, optimal quadrature, optimal quantization, clustering, and optimal mesh generation.
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.
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, and the breeding pits of the male tilapia.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.