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

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

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

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

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

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

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

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

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.