Lloyd's algorithm: Difference between revisions

Revision as of 23:53, 23 August 2016

Revision as of 09:23, 26 February 2017

Line 3:

| direction = vertical

| 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.

| header_align = centerleft

| header_background =

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

| footer_align = center

| footer_background =

| width = 200

Line 12:

| image1 = LloydsMethod1.svg

| alt1 = Lloyd's method, iteration 1

| caption1 = FirstIteration iteration1

| image2 = LloydsMethod2.svg

| alt2 = Lloyd's method, iteration 2

| caption2 = SecondIteration iteration2

| image3 = LloydsMethod3.svg

| alt3 = Lloyd's method, iteration 3

| caption3 = ThirdIteration iteration3

| image4 = LloydsMethod15.svg

| alt4 = Lloyd's method, iteration 15

| caption4 = FifteenthIteration iteration15

}}

In [[computer science]] and [[electrical engineering]], '''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. However, Lloyd's algorithm differs from ''k''-means clustering in that its input is a continuous geometric region rather than a discrete set of points. Thus, when re-partitioning the input, Lloyd's algorithm uses [[Voronoi diagram]]s rather than simply determining the nearest center to each of a finite set of points as the ''k''-means algorithm does.

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]].