Dynamic Voronoi diagrams

A new dynamizing technique is introduced whereby <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> point Voronoi diagrams (both closest and farthest point) can be updated in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(n)</tex> time per insertion or deletion, in the worst case. General properties of these dynamic Voronoi diagrams are explored including a storage/ deletion-time trade-off. In addition, their application to such problems as nearest neighbor search and the 2-minimum spanning circle problem is discussed.