In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Algorithme de Lloyd-Max (fr)
- Algoritmo di Lloyd (it)
- Lloyd's algorithm (en)
- Алгоритм Ллойда (uk)
|
| rdfs:comment
| - In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams. (en)
- En algorithmique et en traitement du signal, l’algorithme de Lloyd-Max est un algorithme qui permet de construire le quantifieur scalaire optimal. C'est donc une méthode pour quantifier un signal en une dimension de manière à minimiser la distorsion, mesurée par l'erreur quadratique moyenne. (fr)
- 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. 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. (it)
- В інформатиці та електротехніці алгоритм Ллойда також відомий як ітерації Вороного чи релаксація. Цей алгоритм названий на честь Стюарта П. Ллойда, який знайшов спосіб знаходження рівномірного розподілу множин точок у підмножини Евклідових просторів і розділення цих підмножин на структуровані опуклі комірки рівномірного розміру. Як і кластеризація методом k-середніх, так і алгоритм Ллойда послідовно знаходять центри кожного набору розподілу, а тоді перерозподіляють вхідні дані відповідно до того, які з цих центрі знаходяться найближче. Відмінність між цими алгоритмами полягає в тому, що вхідними даними для алгоритму Ллойда є неперервна геометрична область, в той час, як для кластеризації методом k-середніх — дискретна множина точок. Тому під час перерозподілу вхідних даних алгоритм Ллойда (uk)
|
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| align
| |
| alt
| - Lloyd's method, iteration 1 (en)
- Lloyd's method, iteration 15 (en)
- Lloyd's method, iteration 2 (en)
- Lloyd's method, iteration 3 (en)
|
| caption
| - Iteration 1 (en)
- Iteration 15 (en)
- Iteration 2 (en)
- Iteration 3 (en)
|
| direction
| |
| footer
| - In the last image, the sites are very near the centroids of the Voronoi cells. A centroidal Voronoi tessellation has been found. (en)
|
| header
| - Example of Lloyd's algorithm. The Voronoi diagram of the current site positions at each iteration is shown. The gray circles denote the centroids of the Voronoi cells. (en)
|
| header align
| |
| image
| - LloydsMethod1.svg (en)
- LloydsMethod15.svg (en)
- LloydsMethod2.svg (en)
- LloydsMethod3.svg (en)
|
| width
| |
| has abstract
| - In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams. Although the algorithm may be applied most directly to the Euclidean plane, similar algorithms may also be applied to higher-dimensional spaces or to spaces with other non-Euclidean metrics. Lloyd's algorithm can be used to construct close approximations to centroidal Voronoi tessellations of the input, which can be used for quantization, dithering, and stippling. Other applications of Lloyd's algorithm include smoothing of triangle meshes in the finite element method. (en)
- En algorithmique et en traitement du signal, l’algorithme de Lloyd-Max est un algorithme qui permet de construire le quantifieur scalaire optimal. C'est donc une méthode pour quantifier un signal en une dimension de manière à minimiser la distorsion, mesurée par l'erreur quadratique moyenne. L'optimalité du quantifieur est assurée par deux conditions sur les niveaux de reconstruction et de décision, découvertes par Lloyd en 1957. Il fournit aussi un algorithme, qui permet de construire itérativement le quantifieur optimal. L'algorithme peut être étendu à la quantification de vecteurs (algorithme de Linde-Buzo-Gray). (fr)
- 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. 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 (dove il punto che genera la partizione è anche il centroide, o baricentro) dell'input, 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. (it)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
