Higher Order Voronoi Diagrams
Demonstration Applet

Instructions
Use the mouse to add and remove points:
  • add a point by left clicking on the drawing area;
  • right click on a point to remove it;
  • you can use the middle button (or mouse wheel) to drag points.
If you move the mouse over a point p, the edges of which p is the k-th nearest neighbour are highlighted. Rolling over a vertex of the diagram will mark the (at least three) k-th nearest neighbours of this point light green and all points that are closer (if k is locked) or further away (if n-k is locked) in dark green.
Adjust the order k of the diagram with the slider or by typing the desired value in the respective textbox. Admissible values lie in the range between 1 and n-1, where n is the number of points.
You can choose between the options "lock k" and "lock n-k". In the first case, the order k of the diagram will be held constant (if possible) as you add or remove points; you get "near" diagrams. Otherwise, k will be increased as you add a point and decreased when you remove one, so n-k is kept constant. This yields as sequence of "far" diagrams.
Clicking on the "clear" button removes all points

Remarks

The applet implements an algorithm that requires O(k(n-k)nlogn) time to create a diagram from scratch. Adding, removing, and particularly dragging a point may be significanlty faster, though. The agorithm works differently in the "lock k" and "lock n-k" modes. In the first case, it keeps a record of an edge's or node's k nearest neigbours. Upon an update, only the parts of the diagram for which the set of the k nearest neighbours is affected need to be newly created. Conversely, computations are based on the n-k furthest neighbours for "lock n-k". So generally, you should expect the algorithm to be faster for small k in "lock k" mode and for small n-k in "lock n-k" mode.
In contrast to the usual convention, the algorithm counts the ends of unbounded edges as voronoi vertices; rays pointing in the same direction end at a common vertex (this ensures that the diagram is always connected). So don't be confused by the number of vertices reported.

References

To find out about higher order Voronoi diagrams (or Voronoi diagrams in general), you may want to have a look at one of the following books and articles:
  • Aurenhammer, F. (1991): "Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure," ACM Computing Surveys, Vol. 23(3), 345-405.
  • Aurenhammer, F. und R. Klein (1996): "Voronoi Diagrams," FernUniversität Hagen Informatik-Berichte Nr. 196.
  • Lee, D.-T. (1982): "On k-Nearest Neighbor Voronoi Diagrams in the Plane," IEEE Transactions on Computers, Vol. C-31(6), 478-487.
  • Okabe, A. u.a. (1999): "Spatial Tessellations: Concepts and Applications of Voronoi Diagrams," John Wiley & Sons, Chichester u.a.
  • Preparata, F.P. und M.I. Shamos (1993): "Computational Geometry. An Introduction," 5th corr. print., Springer, New York.

Written by Andreas Pollak
version 1.0, (c) 2007
This program is part of my diploma thesis in computer science at FernUniversität Hagen, Lehrgebiet Kooperative Systeme, supervised by Dr. Christian Icking.