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
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]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.
Note
[modifica | modifica wikitesto]- ^ a b Stuart P. Lloyd, Least squares quantization in PCM (PDF), in IEEE Transactions on Information Theory, vol. 28, n. 2, 1982, pp. 129–137, DOI:10.1109/TIT.1982.1056489.
- ^ Qiang Du, Vance Faber e Max Gunzburger, Centroidal Voronoi tessellations: applications and algorithms, in SIAM Review, vol. 41, n. 4, 1999, pp. 637–676, Bibcode:1999SIAMR..41..637D, DOI:10.1137/S0036144599352836.
- ^ Joel Max, Quantizing for minimum distortion, in IRE Transactions on Information Theory, vol. 6, n. 1, 1960, pp. 7–12, DOI:10.1109/TIT.1960.1057548.
Altri progetti
[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su algoritmo di Lloyd
