Iteratives Verfahren, das eine Menge von Erzeugungspunkten durch wiederholtes Ersetzen jedes Punktes durch den Schwerpunkt seiner Voronoi-Zelle neu platziert, im Grenzfall zentroidale Voronoi-Zerlegungen erzeugt und eine Quantisierungsenergie misst und reduziert (mittlere quadrierte Distanz zu den Generatoren).

Prinzip

Die Lloyd-Iteration wirkt gradientenabstiegsähnlich auf die Quantisierungsenergie (CVT): Das Verschieben jedes Generators zum Massenzentroid seiner Voronoi-Region verringert die L^2-Quantisierungsfunktional, fördert gleichmäßige Verteilung in konvexen Gebieten und konvergiert unter Regularitätsannahmen zu einer (lokalen) zentroidalen Konfiguration.

Demonstration

Beginne mit zufälligen Punkten im Einheitsquadrat, berechne die Voronoi-Partition, ersetze jeden Punkt durch den Zellschwerpunkt und iteriere; nach vielen Schritten nähern sich die Punkte einem hexagonalen Gittermuster im Inneren an und sampeln das Gebiet quasi-gleichmäßig. Auf gekrümmten Flächen werden Schwerpunkte bezüglich Flächenmaß berechnet und Updates müssen auf die Oberfläche projiziert werden.

Fehlanwendung

Lloyd ohne Gebietsbeschränkungen oder Merkmalsprojektion auszuführen kann Punkte aus dem zulässigen Bereich treiben; Lloyd als Allzweckoptimierer zu verwenden ignoriert, dass er nur die L^2-Energie minimiert, langsam konvergieren kann, in lokale Minima fallen oder Randverteilungen zerstören kann, falls Schwerpunkte naiv berechnet werden.

Konsequenz

Richtig angewendet produziert Lloyds Algorithmus gut verteilte Stichprobenpunkte, verbessert Mesh-Qualität für centroidales Remeshing und reduziert Quantisierungsfehler; er kann jedoch viele Iterationen, sorgfältige Behandlung von Rändern und Hindernissen sowie Initialisierungsstrategien erfordern, um schlechte lokale Minima zu vermeiden.

Umkehrung

Der inverse Prozess (Wiederherstellen früherer Generatorpositionen aus Schwerpunkten) ist nicht eindeutig, da Informationen durch Mittelung verloren gehen; das Maximieren der Quantisierungsfunktional (Punkte zur Clusterbildung bewegen) ergibt das gegenteilige, nicht uniforme und instabile Verhalten unter denselben Updates.

Abgrenzung

Gilt für Gebiete, in denen Voronoi-Zellen und Schwerpunkte bezüglich einer gewählten Maßnahme (euklidische Fläche, Flächenmaß oder gewichtete Dichte) wohl definiert sind; ausgenommen sind Fälle mit singulären Maßen, zusammenhangslosen zulässigen Mengen ohne Projektion oder Beschränkungen, die die Verlagerung zu Schwerpunkten verbieten (harte Hindernisse, feste Merkmals-Punkte).

Semantische Spannung

Setze Lloyds Algorithmus in Beziehung zu k-means: Mathematisch identisch mit Batch-k-means für L^2-Verlust im kontinuierlichen Setting, aber Lloyd wird für geometrische Stichproben und CVT-Konstruktion eingesetzt, während k-means Datenclustering verfolgt; Lloyd zielt auf zentroidale Regularität, nicht notwendigerweise auf wahrnehmungsbasierte Clusterbildung.

Synthese

Lloyd-Algorithmus ist das einfache iterative, lokal-zu-global Verfahren, das die L^2-Quantisierungsenergie durch Verlagerung der Generatoren zu Voronoi-Schwerpunkten verringert: Voronoi-Zellen berechnen, Punkte durch Schwerpunkte ersetzen (mit Projektion und Gewichtung falls nötig) und iterieren bis zu einer zentroidalen Voronoi-Zerlegung oder bis zufriedenstellender Stichprobenverteilung.