Lloyd's algorithm: Difference between revisions

Revision as of 22:13, 5 September 2013

Revision as of 22:31, 5 September 2013

Line 53:

==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 getfind squarea tiling of an image by approximately-gridsquare tiles otherwhose thanorientation hexagonsaligns with features of an image, which he used to simulate the construction of tiled [[Manhattan metricmosaic]]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 usedappropriate to choose the minimizer of average squared distance as the representative point, in place of the centroid.<ref name="h01dew10"/>

== See also ==

Line 74:

| volume = 19

| year = 2000}}.</ref>

<ref name="dew10">{{citation

| last1 = Dickerson | first1 = Matthew T. | author1-link = Matthew T. Dickerson

| last2 = Eppstein | first2 = David | author2-link = David Eppstein

| last3 = Wortman | first3 = Kevin A.

| arxiv = 0812.0607

| contribution = Planar Voronoi diagrams for sums of convex functions, smoothed distance and dilation

| doi = 10.1109/ISVD.2010.12

| pages = 13–22

| title = Proc. 7th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2010)

| year = 2010}}.</ref>

<ref name="dej06">{{citation

| last1 = Du | first1 = Qiang