Algoritmo di Lloyd

Esempio di applicazione dell'algoritmo. Sono mostrati i diagrammi di Voronoi dei punti. I segni positivi indicano i baricentri delle partizioni di Voronoi

Iterazione 1

Iterazione 2

Iterazione 3

Iterazione 15

In ingegneria elettrica e informatica, l'algoritmo di Lloyd, noto anche come iterazione (o rilassamento) di Voronoi, è un algoritmo che prende il nome da Stuart P. Lloyd per trovare insiemi di punti equidistanti in sottoinsiemi di spazi euclidei e partizioni di questi sottoinsiemi in celle.^[1] Come il simile K-means, questo algoritmo trova ripetutamente il baricentro di ciascun insieme nella partizione e quindi ripartiziona l'insieme dei punti in base a quale di questi baricentri è più vicino. In questa impostazione, l'operazione media è un integrale su una regione di spazio e l'operazione del centroide più vicino risulta nei diagrammi di Voronoi.

Sebbene l'algoritmo possa essere applicato più direttamente al piano euclideo, algoritmi simili possono essere applicati anche a spazi di dimensioni superiori o a spazi con altre metriche non euclidee. L'algoritmo di Lloyd può essere utilizzato per costruire approssimazioni affidabili delle partizioni di Voronoi centroidali (dove il punto che genera la partizione è anche il centroide, o baricentro) dell'input,^[2] che possono essere utilizzate per la quantizzazione, il dithering e lo stippling. L'algoritmo può essere applicato nello smussamento delle mesh triangolari nel metodo degli elementi finiti.

Storia

L'algoritmo è stato proposto per la prima volta da Stuart P. Lloyd dei Bell Laboratories nel 1957 come tecnica per la modulazione a impulsi codificati. Il lavoro di Lloyd divenne ampiamente diffuso ma non fu pubblicato fino al 1982.^[1] Un algoritmo simile è stato sviluppato indipendentemente da Joel Max e pubblicato nel 1960,^[3] motivo per cui l'algoritmo è talvolta indicato come algoritmo di Lloyd-Max.

Descrizione

L'algoritmo di Lloyd inizia con un posizionamento iniziale di un certo numero k di siti nel dominio di input. Quindi viene eseguita ripetutamente la seguente fase di rilassamento:

Viene calcolato il diagramma di Voronoi dei k siti.
Ogni cella del diagramma di Voronoi è integrata e viene calcolato il baricentro.
Ogni sito viene quindi spostato al baricentro della sua cella di Voronoi.

Poiché gli algoritmi per la costruzione dei diagrammi di Voronoi possono essere altamente non banali, specialmente per input di dimensione superiore a due, i passaggi per calcolarli e trovare i baricentri esatti delle celle possono essere sostituiti da un'approssimazione.