Editing Voronoi diagram (section)

==Higher-order Voronoi diagrams==
Although a normal Voronoi cell is defined as the set of points closest to a single point in ''S'', an ''n''th-order Voronoi cell is defined as the set of points having a particular set of ''n'' points in ''S'' as its ''n'' nearest neighbors. Higher-order Voronoi diagrams also subdivide space.

Higher-order Voronoi diagrams can be generated recursively.  To generate the ''n''<sup>th</sup>-order Voronoi diagram from set&nbsp;''S'', start with the (''n''&nbsp;−&nbsp;1)<sup>th</sup>-order diagram and replace each cell generated by ''X''&nbsp;=&nbsp;{''x''<sub>1</sub>,&nbsp;''x''<sub>2</sub>,&nbsp;...,&nbsp;''x''<sub>''n''−1</sub>} with a Voronoi diagram generated on the set&nbsp;''S''&nbsp;−&nbsp;''X''.

===Farthest-point Voronoi diagram===
For a set of ''n'' points, the (''n''&nbsp;−&nbsp;1)<sup>th</sup>-order Voronoi diagram is called a farthest-point Voronoi diagram.

For a given set of points ''S''&nbsp;=&nbsp;{''p''<sub>1</sub>,&nbsp;''p''<sub>2</sub>,&nbsp;...,&nbsp;''p''<sub>''n''</sub>}, the farthest-point Voronoi diagram divides the plane into cells in which the same point of ''P'' is the farthest point. A point of ''P'' has a cell in the farthest-point Voronoi diagram if and only if it is a vertex of the [[convex hull]] of ''P''. Let ''H''&nbsp;=&nbsp;{''h''<sub>1</sub>,&nbsp;''h''<sub>2</sub>,&nbsp;...,&nbsp;''h''<sub>''k''</sub>} be the convex hull of ''P''; then the farthest-point Voronoi diagram is a subdivision of the plane into ''k'' cells, one for each point in ''H'', with the property that a point ''q'' lies in the cell corresponding to a site ''h''<sub>''i''</sub> if and only if d(''q'', ''h''<sub>''i''</sub>) > d(''q'', ''p''<sub>''j''</sub>) for each ''p''<sub>''j''</sub>&nbsp;∈&nbsp;''S'' with ''h''<sub>''i''</sub> ≠ ''p''<sub>''j''</sub>, where d(''p'', ''q'') is the [[Euclidean distance]] between two points ''p'' and&nbsp;''q''.<ref name="berg2008">{{cite book |year=2008 |title=Computational Geometry |isbn=978-3-540-77974-2 |publisher=[[Springer-Verlag]] |edition=Third |first1=Mark |last1=de Berg |first2=Marc |last2=van Kreveld |first3=Mark |last3=Overmars |first4=Otfried |last4=Schwarzkopf |author-link1=Mark de Berg |author-link2=Marc van Kreveld |author-link3=Mark Overmars |author-link4=Otfried Schwarzkopf}} 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.</ref><ref>{{cite journal |first=Sven |last=Skyum |title=A simple algorithm for computing the smallest enclosing circle |journal=Information Processing Letters |volume=37 |issue=3 |date=18 February 1991 |pages=121–125 |doi=10.1016/0020-0190(91)90030-L}}, contains a simple algorithm to compute the farthest-point Voronoi diagram.</ref>

The boundaries of the cells in the farthest-point Voronoi diagram have the structure of a [[Real tree|topological tree]], with infinite [[Ray (mathematics)|rays]] as its leaves. Every finite tree is isomorphic to the tree formed in this way from a farthest-point Voronoi diagram.<ref>{{cite conference
 | last1 = Biedl | first1 = Therese | author-link = Therese Biedl
 | last2 = Grimm | first2 = Carsten
 | last3 = Palios | first3 = Leonidas
 | last4 = Shewchuk | first4 = Jonathan | author4-link = Jonathan Shewchuk
 | last5 = Verdonschot | first5 = Sander
 | contribution = Realizing farthest-point Voronoi diagrams
 | title = Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)
 | year = 2016}}</ref>