Content deleted Content added
m →References: Added 1 doi to a journal cite using AWB (10216) |
→Convergence: optimization for convergence |
||
Line 44:
Each time a relaxation step is performed, the points are left in a slightly more even distribution: closely spaced points move farther apart, and widely spaced points move closer together. In one dimension, this algorithm has been shown to converge to a centroidal Voronoi diagram, also named a [[centroidal Voronoi tessellation]].<ref name="dej06"/> In higher dimensions, some slightly weaker convergence results are known.<ref name="sg86"/><ref name="ejr09"/>
The algorithm converges slowly or, due to limitations in numerical precision, may not converge. Therefore, real-world applications of Lloyd's algorithm typically stop once the distribution is "good enough." One common termination criterion is to stop when the maximum distance moved by any site in an iteration falls below a preset threshold. Convergence can be accelerated by over-relaxing the points, which is done by moving each point '''ω''' times the distance to the center of mass, typically using a value slightly less than 2 for '''ω'''.<ref>Xiao, Xiao. "Over-relaxation Lloyd method for computing centroidal Voronoi tessellations." (2010).</ref>
==Applications==
| |||