Editing Voronoi diagram (section)

==Algorithms==
Several efficient algorithms are known for constructing Voronoi diagrams, either directly (as the diagram itself) or indirectly by starting with a [[Delaunay triangulation]] and then obtaining its dual.
Direct algorithms include [[Fortune's algorithm]], an [[big O notation|O]](''n'' log(''n'')) algorithm for generating a Voronoi diagram from a set of points in a plane.
[[Bowyer–Watson algorithm]], an [[big O notation|O]](''n'' log(''n'')) to [[big O notation|O]](''n''<sup>2</sup>) algorithm for generating a Delaunay triangulation in any number of dimensions, can be used in an indirect algorithm for the Voronoi diagram. The [[Jump flooding algorithm|Jump Flooding Algorithm]] can generate approximate Voronoi diagrams in constant time and is suited for use on commodity graphics hardware.<ref>{{cite conference
 | last1 = Rong | first1 = Guodong
 | last2 = Tan | first2 = Tiow Seng
 | editor1-last = Olano | editor1-first = Marc
 | editor2-last = Séquin | editor2-first = Carlo H.
 | contribution = Jump flooding in GPU with applications to Voronoi diagram and distance transform
 | contribution-url = https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf
 | doi = 10.1145/1111411.1111431
 | pages = 109–116
 | publisher = ACM
 | title = Proceedings of the 2006 Symposium on Interactive 3D Graphics, SI3D 2006, March 14-17, 2006, Redwood City, California, USA
 | year = 2006| isbn = 1-59593-295-X
 }}</ref><ref>{{Cite web|url=https://www.shadertoy.com/view/4syGWK|title = Shadertoy}}</ref>

[[Lloyd's algorithm]] and its generalization via the [[Linde–Buzo–Gray algorithm]] (aka [[k-means clustering]]) use the construction of Voronoi diagrams as a subroutine.
These methods alternate between steps in which one constructs the Voronoi diagram for a set of seed points, and steps in which the seed points are moved to new locations that are more central within their cells. These methods can be used in spaces of arbitrary dimension to iteratively converge towards a specialized form of the Voronoi diagram, called a [[Centroidal Voronoi tessellation]], where the sites have been moved to points that are also the geometric centers of their cells.