En geometría , una teselación centroidal de Voronoi ( CVT ) es un tipo especial de teselación de Voronoi en la que el punto generador de cada celda de Voronoi es también su centroide (centro de masa). Puede verse como una partición óptima correspondiente a una distribución óptima de generadores. Se pueden utilizar varios algoritmos para generar teselaciones centroidales de Voronoi, incluido el algoritmo de Lloyd para agrupación de K-medias o métodos Quasi-Newton como BFGS . [1]
La conjetura de Gersho, probada para una y dos dimensiones, dice que "asintóticamente hablando, todas las células del CVT óptimo, aunque forman un mosaico , son congruentes con una célula básica que depende de la dimensión". [2]
En dos dimensiones, la celda básica para la CVT óptima es un hexágono regular , ya que se ha demostrado que es el paquete de círculos más denso en el espacio euclidiano 2D. Su equivalente tridimensional es el panal dodecaédrico rómbico , derivado del empaquetamiento de esferas más denso en el espacio euclidiano 3D.
Las teselaciones centroidales de Voronoi son útiles en compresión de datos , cuadratura óptima , cuantificación óptima , agrupación y generación de malla óptima. [3]
Un diagrama de Voronoi centroidal ponderado es un CVT en el que cada centroide se pondera según una función determinada. Por ejemplo, una imagen en escala de grises se puede utilizar como función de densidad para ponderar los puntos de una CVT, como forma de crear punteado digital . [4]
Muchos patrones observados en la naturaleza se aproximan estrechamente mediante una teselación centroidal de Voronoi. Ejemplos de esto incluyen la Calzada del Gigante , las células de la córnea , [5] y las fosas de reproducción de la tilapia macho . [3]