Algoritmo di Lloyd: differenze tra le versioni

Versione delle 22:08, 18 gen 2022

Versione attuale delle 23:27, 16 mar 2025

(4 versioni intermedie di 2 utenti non mostrate)

Riga 1:

{{Immagine multipla

|didascalia1 = Iterazione 1

|align = right

|immagine4 = LloydsMethod15.svg

|caption1 = Iteration 1

|didascalia3 = Iterazione 3

|alt4 = Lloyd's method, iteration 15

|image4immagine3 = LloydsMethod15LloydsMethod3.svg

|didascalia2 = Iterazione 2

|caption3 = Iteration 3

|immagine2 = LloydsMethod2.svg

|alt3 = Lloyd's method, iteration 3

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

|image3 = LloydsMethod3.svg

|alignallinea = right

|caption2 = Iteration 2

|directiondirezione = vertical

|alt2 = Lloyd's method, iteration 2

|image2immagine1 = LloydsMethod2LloydsMethod1.svg

|didascalia4 = Iterazione 15

|alt1 = Lloyd's method, iteration 1

|direction = vertical

|image1 = LloydsMethod1.svg

|width = 200

|footer_background =

|footer_align =

|footer = In the last image, the points are very near the centroids of the Voronoi cells. A centroidal Voronoi tessellation has been found.

|header_background =

|header_align = left

|header = Example of Lloyd's algorithm. The Voronoi diagram of the current points at each iteration is shown. The plus signs denote the centroids of the Voronoi cells.

|caption4 = Iteration 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 ==

Riga 40 ⟶ 30:

== Note ==

<references />

== Altri progetti ==

{{interprogetto}}

{{Portale|informatica|elettronica}}

[[Categoria:Algoritmi geometrici]]