Lloyd's algorithm: Difference between revisions

Revision as of 01:26, 16 July 2015

Revision as of 21:43, 21 October 2015

Line 27:

}}

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

Line 50:

In the [[finite element method]], an input ___domain with a complex geometry is partitioned into elements with simpler shapes; for instance, two-dimensional domains (either subsets of the Euclidean plane or surfaces in three dimensions) are often partitioned into triangles. It is important for the convergence of the finite element methods that these elements be well shaped; in the case of triangles, often elements that are nearly equilateral triangles are preferred. Lloyd's algorithm

can be used to smooth a mesh generated by some other algorithm, moving its vertices and changing the connection pattern among its elements in order to produce triangles that are more closely equilateral.<ref name="dg02"/> These applications typically use a smaller number of iterations of Lloyd's algorithm, stopping it to convergence, in order to preserve other features of the mesh such as differences in element size in different parts of the mesh. In contrast to a different smoothing method, [[Laplacian smoothing]] (in which mesh vertices are moved to the average of their neighbors' positions), Lloyd's algorithm can change the topology of the mesh, leading to more nearly- equilateral elements as well as avoiding the problems with tangling that can arise with Laplacian smoothing. However, Laplacian smoothing can be applied more generally to meshes with non-triangular elements.

==Different distances==

Lloyd's algorithm is usually used in a [[Euclidean space]]. The Euclidean distance plays two roles in the algorithm: it is used to define the Voronoi cells, but it also corresponds to the choice of the centroid as the representative point of each cell, since the centroid is the point that minimizes the average squared Euclidean distance to the points in its cell. Alternative distances, and alternative central points than the centroid, may be used instead. For example, {{harvtxt|Hausner|2001}} used a variant of the [[Manhattan metric]] (with locally- varying orientations) to find a tiling of an image by approximately- square tiles whose orientation aligns with features of an image, which he used to simulate the construction of tiled [[mosaic]]s.<ref name="h01"/> In this application, despite varying the metric, Hausner continued to use centroids as the representative points of their Voronoi cells. However, for metrics that differ more significantly from Euclidean, it may be appropriate to choose the minimizer of average squared distance as the representative point, in place of the centroid.<ref name="dew10"/>

== See also ==

* The [[Linde–Buzo–Gray algorithm]], a generalization of this algorithm for vector quantization

* [[Farthest-first traversal]], a different method for generating evenly- spaced points in geometric spaces

* [[Mean shift]], a related method for finding maxima of a density function