Lloyd's algorithm
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.
- Align
- enleft
- Alt
- enLloyd's method, iteration 1
- enLloyd's method, iteration 15
- enLloyd's method, iteration 2
- enLloyd's method, iteration 3
- Caption
- enIteration 1
- enIteration 15
- enIteration 2
- enIteration 3
- Comment
- enIn 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.
- Depiction
- Direction
- enhorizontal
- Footer
- enIn the last image, the sites are very near the centroids of the Voronoi cells. A centroidal Voronoi tessellation has been found.
- Has abstract
- enIn 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.
- Header
- enExample 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.
- HeaderAlign
- enleft
- Hypernym
- Algorithm
- Image
- enLloydsMethod1.svg
- enLloydsMethod15.svg
- enLloydsMethod2.svg
- enLloydsMethod3.svg
- Is primary topic of
- Lloyd's algorithm
- Label
- enLloyd's algorithm
- Link from a Wikipage to an external page
- demogng.de/js/demogng.html%3Fmodel=LBG&showAutoRestart&showVoronoi
- Link from a Wikipage to another Wikipage
- Bell Labs
- Blue noise
- Category:Geometric algorithms
- Category:Optimization algorithms and methods
- Centroid
- Centroidal Voronoi tessellation
- Colors of noise
- Computer science
- Data compression
- Dithering
- Electrical engineering
- Euclidean distance
- Euclidean plane
- Euclidean space
- Farthest-first traversal
- Finite element method
- Information theory
- K-means++
- K-means clustering
- Laplacian smoothing
- Linde–Buzo–Gray algorithm
- Lp space
- Manhattan metric
- Mean shift
- Monte Carlo methods
- Mosaic
- Non-Euclidean geometry
- Pulse-code modulation
- Quantization (signal processing)
- Stippling
- Tetrahedron
- Triangle
- Triangle mesh
- Voronoi diagram
- Z-buffering
- SameAs
- 2dx4T
- Algorithme de Lloyd-Max
- Algoritmo di Lloyd
- Lloyd's algorithm
- Lloydi algoritm
- m.07rd1w
- Q2835805
- Алгоритм Ллойда
- אלגוריתם לויד-מקס
- لائیڈ الخوارزم
- Subject
- Category:Geometric algorithms
- Category:Optimization algorithms and methods
- Thumbnail
- WasDerivedFrom
- Lloyd's algorithm?oldid=1119165105&ns=0
- Width
- 200
- WikiPageLength
- 15709
- Wikipage page ID
- 2607912
- Wikipage revision ID
- 1119165105
- WikiPageUsesTemplate
- Template:Clear
- Template:Harvtxt
- Template:Math
- Template:Multiple image
- Template:Reflist