En geometría , una teselación de Voronoi centroidal ( 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 que corresponde a una distribución óptima de generadores. Se pueden utilizar varios algoritmos para generar teselaciones de Voronoi centroidales, incluido el algoritmo de Lloyd para agrupamiento 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 celdas de la CVT óptima, mientras forman una teselación , son congruentes con una celda 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 empaquetamiento más denso de círculos en el espacio euclidiano 2D. Su equivalente tridimensional es el panal dodecaédrico rómbico , derivado del empaquetamiento más denso de esferas en el espacio euclidiano 3D.
Las teselaciones de Voronoi centroidales son útiles en la compresión de datos , la cuadratura óptima , la cuantificación óptima , la agrupación y la generación óptima de mallas. [3]
Un diagrama de Voronoi centroidal ponderado es un diagrama de Voronoi de curvatura continua 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 un diagrama de Voronoi de curvatura continua, como una forma de crear punteado digital . [4]
Muchos patrones que se observan en la naturaleza se aproximan estrechamente a una teselación de Voronoi centroidal. Algunos ejemplos de esto incluyen la Calzada del Gigante , las células de la córnea [5] y los fosos de reproducción de la tilapia macho [3] .