Lloyd's algorithm: Difference between revisions

Revision as of 02:04, 11 March 2022

Revision as of 11:01, 1 July 2022

Line 1:

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 space]]s and partitions of these subsets into well-shaped and uniformly sized convex cells.<ref name="l82"/> Like the closely related [[k-means clustering|''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 diagram]]s.

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 geometry|non-Euclidean]] metrics. Lloyd's algorithm can be used to construct close approximations to [[centroidal Voronoi tessellation]]s of the input,<ref name="dfg99"/> which can be used for [[Quantization (signal processing)|quantization]], [[dithering]], and [[stippling]]. Other applications of Lloyd's algorithm include smoothing of [[triangle mesh]]es in the [[finite element method]].

{{multiple image

| align = right

| direction = verticalhorizontal

| header = Example of Lloyd's algorithm. The Voronoi diagram of the current pointssite positions (red) at each iteration is shown. The plusgray signscircles denote the centroids of the Voronoi cells.

| header_align = left

| header_background =

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

| footer_align =

| footer_background =

Line 26 ⟶ 30:

| caption4 = Iteration 15

}}

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 space]]s and partitions of these subsets into well-shaped and uniformly sized convex cells.<ref name="l82"/> Like the closely related [[k-means clustering|''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 diagram]]s.

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 geometry|non-Euclidean]] metrics. Lloyd's algorithm can be used to construct close approximations to [[centroidal Voronoi tessellation]]s of the input,<ref name="dfg99"/> which can be used for [[Quantization (signal processing)|quantization]], [[dithering]], and [[stippling]]. Other applications of Lloyd's algorithm include smoothing of [[triangle mesh]]es in the [[finite element method]].

==History==