Live briefing
Everything about Lloyd's algorithm
Algorithm used for points in euclidean space
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. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Lloyd's algorithmA 5-minute orientation
- Skim a recent paper: Adapting the Harrow-Hassidim-Lloyd algorithm to quantum many-body theoryInfluential work since 2022
- Pick up a classic book: Biomedical image analysis and mining techniques for improved health outcomesThe most-reprinted book on the subject
- Read the landmark paper: Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi TessellationsCited 273 times
- Go sideways: Centroidal Voronoi tessellationA closely related topic
- Go sideways: Delaunay triangulationA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🏆 Landmark papers (most cited)
Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
Global convergence and empirical consistency of the generalized Lloyd algorithm
The Design of Predictive Trellis Waveform Coders Using the Generalized Lloyd Algorithm
A genetic Lloyd-Max image quantization algorithm
A modification of the Lloyd algorithm for k-anonymous quantization
A Generalized Lloyd-Type Algorithm for Adaptive Transform Coder Design
Pointwise Convergence of the Lloyd I Algorithm in Higher Dimension
Lloyd–Max's Algorithm Implementation in Speech Coding Algorithm Based on Forward Adaptive Technique
🆕 Influential since 2022
Adapting the Harrow-Hassidim-Lloyd algorithm to quantum many-body theory
Harrow-Hassidim-Lloyd algorithm without ancilla postselection
Digital-Analog Co-Design of the Harrow-Hassidim-Lloyd Algorithm
K-bMOM: A robust Lloyd-type clustering algorithm based on bootstrap median-of-means
Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large condition numbers
📚 Books worth reading
- 📕Biomedical image analysis and mining techniques for improved health outcomesWahiba Ben Abdessalem Karaa, Nilanjan Dey · 2016
Diabetes and ocular diseaseWilliam E. Smiddy · 2008- 📕Know thisJohn Brockman · 2017
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Centroidal Voronoi tessellation Three centroidal Voronoi tessellations of five points in a square In geometry, a centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation…
- Delaunay triangulation In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles…
- Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation…
- K-means clustering k-means clustering is a method of vector quantization, originally from signal processing, that aims to partition n observations into k clusters in which…
- Computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms that can be stated in terms of geometry. Some purely geometrical…
- Power diagram In computational geometry, a power diagram, also called a Laguerre–Voronoi diagram, Dirichlet cell complex, radical Voronoi tesselation or a sectional…
- Vector quantization Vector quantization (VQ) is a classical quantization technique from signal processing that allows the modeling of probability density functions by the…
- Weighted Voronoi diagram In mathematics, a weighted Voronoi diagram in n dimensions is a generalization of a Voronoi diagram. The Voronoi cells in a weighted Voronoi diagram are…