## [Algoritmo de Lloyd](/es/node/62735) Definición Esquema iterativo que reubica un conjunto de puntos generadores sustituyendo repetidamente cada punto por el centroide de su celda de Voronoi, produciendo en el límite teselaciones de Voronoi centroidales y reduciendo una energía de cuantización que mide la distancia cuadrática media a los generadores. ## Principio Principio La iteración de Lloyd es similar a descenso por gradiente sobre la energía de cuantización (CVT): mover cada generador al centroide de su región de Voronoi disminuye la funcional L^2 de cuantización, promueve un espaciado uniforme en dominios convexos y converge bajo supuestos de regularidad a una configuración centroidal (local). ## Demostración Demostración Partiendo de puntos aleatorios en el cuadrado unidad, calcular la partición de Voronoi, reemplazar cada punto por el centroide de su celda e iterar; tras muchas etapas los puntos aproximan un patrón hexagonal en el interior y muestrean el dominio casi uniformemente. En una superficie curva, los centroides se calculan respecto a la medida de área de la superficie y las actualizaciones deben proyectarse de nuevo sobre la superficie. ## Aplicación incorrecta Aplicación incorrecta Ejecutar Lloyd sin imponer restricciones de dominio o proyección de características puede desplazar puntos fuera de la región admisible; usar Lloyd como optimizador universal descuida que solo disminuye la energía L^2 y puede converger despacio, quedar atrapado en mínimos locales o destruir patrones de muestreo de contorno si los centroides se calculan de forma ingenua. ## Consecuencia Consecuencia Aplicado correctamente, el algoritmo de Lloyd produce puntos de muestreo bien espaciados, mejora la calidad del mallado para remallado centroidal y reduce el error de cuantización; sin embargo, puede requerir muchas iteraciones, manejo cuidadoso de contornos y obstáculos, y estrategias de inicialización para evitar malos mínimos locales. ## Inversión Inversión El proceso inverso (recuperar posiciones previas de generadores a partir de centroides) no está definido de forma única porque la información se pierde por promediado; maximizar la funcional de cuantización (empujar puntos a agruparse) conduce a distribuciones opuestas, no uniformes e inestables ante las mismas actualizaciones. ## Límite Límite Se aplica a dominios donde las celdas de Voronoi y centroides estén bien definidos para la medida elegida (área euclidiana, área de superficie o densidad ponderada); excluye casos con medidas singulares, conjuntos admisibles desconectados sin proyección o restricciones que impidan la reubicación por centroide (obstáculos rígidos, puntos de característica fijos). ## Tensión semántica Tensión semántica Relacionar Lloyd con k-means: matemáticamente idénticos al k-means por lotes para la pérdida L^2 en entornos continuos, pero Lloyd se usa para muestreo geométrico y construcción de CVT mientras k-means apunta al clustering de datos; Lloyd busca regularidad centroidal, no necesariamente agrupamientos perceptuales. ## Síntesis Síntesis El algoritmo de Lloyd es el procedimiento iterativo simple y local-a-global que reduce la energía de cuantización L^2 moviendo generadores hacia centroides de Voronoi: calcular celdas de Voronoi, reemplazar puntos por centroides (con proyección y ponderación si procede) e iterar hasta obtener una teselación de Voronoi centroidal o una distribución de muestreo satisfactoria.