Schéma itératif qui repositionne un ensemble de points générateurs en remplaçant à chaque étape chaque point par le centroïde de sa cellule de Voronoï, produisant en limite des tessellations de Voronoï centroïdales et réduisant une énergie de quantification mesurant la distance quadratique moyenne aux générateurs.

Principe

L'itération de Lloyd ressemble à une descente de gradient sur l'énergie de quantification (CVT) : déplacer chaque générateur vers le centroïde de sa région de Voronoï diminue la fonctionnelle de quantification L^2, favorise un espacement uniforme dans des domaines convexes et converge sous hypothèses de régularité vers une configuration centroïdale (locale).

Démonstration

Initialiser par des points aléatoires dans le carré unité, calculer la partition de Voronoï, remplacer chaque point par le centroïde de sa cellule et itérer ; après de nombreuses étapes, les points s'approchent d'un réseau hexagonal à l'intérieur et échantillonnent le domaine quasi-uniformément. Sur une surface courbe, les centroïdes se calculent par rapport à la mesure de surface et les mises à jour doivent être projetées sur la surface.

Mauvaise application

Exécuter Lloyd sans imposer contraintes de domaine ou projection des caractéristiques peut faire sortir des points de la région admissible ; utiliser Lloyd comme optimiseur universel ignore qu'il ne diminue que l'énergie L^2, peut converger lentement, rester bloqué dans des minima locaux ou dégrader l'échantillonnage des bords si les centroïdes sont calculés naïvement.

Conséquence

Bien appliqué, l'algorithme de Lloyd produit des points d'échantillonnage bien espacés, améliore la qualité de maillage pour le remeshing centroidal et réduit l'erreur de quantification ; il peut cependant nécessiter de nombreuses itérations, une gestion soignée des bords et des obstacles, et des stratégies d'initialisation pour éviter de mauvais minima locaux.

Inversion

Le processus inverse (récupérer les positions antérieures des générateurs à partir des centroïdes) n'est pas unique car l'information est perdue par le moyennage ; maximiser la fonctionnelle de quantification (pousser les points à se regrouper) donne des distributions opposées, non uniformes et instables vis-à-vis des mêmes mises à jour.

Limite

S'applique à des domaines où les cellules de Voronoï et les centroïdes sont bien définis pour une mesure choisie (aire euclidienne, aire de surface ou densité pondérée) ; exclut les cas de mesures singulières, d'ensembles admissibles déconnectés sans projection ou de contraintes empêchant le déplacement par centroïde (obstacles durs, points caractéristiques fixes).

Tension sémantique

Relier l'algorithme de Lloyd au k-means : identiques mathématiquement au k-means en mode batch pour la perte L^2 en contexte continu, mais Lloyd s'utilise pour l'échantillonnage géométrique et la construction de CVT tandis que k-means vise le clustering de données ; Lloyd cherche la régularité centroïdale, pas nécessairement un clustering perceptuel.

Synthèse

L'algorithme de Lloyd est la procédure itérative simple, locale-vers-global qui diminue l'énergie de quantification L^2 en déplaçant les générateurs vers les centroïdes de Voronoï : calculer les cellules de Voronoï, remplacer les points par leurs centroïdes (avec projection et pondération si nécessaire), et itérer jusqu'à obtenir une tessellation de Voronoï centroïdale ou un échantillonnage satisfaisant.