Algoritmo di Lloyd: differenze tra le versioni

Versione delle 20:25, 21 gen 2023

Versione attuale delle 23:27, 16 mar 2025

Riga 12:

|didascalia4 = Iterazione 15

}}

In [[Elettrotecnica|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 [[Spazio euclideo|spazi euclidei]] e partizioni di questi sottoinsiemi in celle.<ref name="l82">{{cita pubblicazione|autore=Stuart P. Lloyd|anno=1982|titolo=Least squares quantization in PCM|rivista=[[IEEE Transactions on Information Theory]]|volume=28|numero=2|pp=129–137129-137|doi=10.1109/TIT.1982.1056489|url=http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf}}</ref> Come il simile [[K-means]], questo algoritmo trova ripetutamente il [[Baricentro (geometria)|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 [[Diagramma di Voronoi|diagrammi di Voronoi]].

Sebbene l'algoritmo possa essere applicato più direttamente al [[Piano (geometria)|piano euclideo]], algoritmi simili possono essere applicati anche a spazi di dimensioni superiori o a spazi con altre metriche [[Geometria non euclidea|non euclidee.]] L'algoritmo di Lloyd può essere utilizzato per costruire approssimazioni affidabili delle [[Tassellatura di Voronoi centroidale|partizioni di Voronoi centroidali]] (dove il punto che genera la partizione è anche il centroide, o baricentro) dell'input,<ref name="dfg99">{{cita pubblicazione|autore=Qiang Du|autore2=Vance Faber|autore3=Max Gunzburger|anno=1999|titolo=Centroidal Voronoi tessellations: applications and algorithms|rivista=SIAM Review|volume=41|numero=4|pp=637–676637-676|doi=10.1137/S0036144599352836|bibcode=1999SIAMR..41..637D}}</ref> che possono essere utilizzate per la [[Quantizzazione (elettronica)|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.<ref name="l82" /> Un algoritmo simile è stato sviluppato indipendentemente da Joel Max e pubblicato nel 1960,<ref name="m60">{{cita pubblicazione|autore=Joel Max|anno=1960|titolo=Quantizing for minimum distortion|rivista=[[IRE Transactions on Information Theory]]|volume=6|numero=1|pp=7–127-12|doi=10.1109/TIT.1960.1057548}}</ref> motivo per cui l'algoritmo è talvolta indicato come algoritmo di Lloyd-Max.

== Descrizione ==