Computational Geometry - An Introduction Through Randomized Algorithms; Mulmuley; 1994; pp 135-
Proposition 4.2.2: The total cost of maintaining a Voronoi diagram in a given update sequence is proportional to the total structural change during that sequence. This ignores a logarithmic factor in the cost of a deletion. It also ignores the cost of locating a conflicting vertex during addition. The expected (total) structural change during a random \(\) -sequence is \(\) .
Dynamic Algorithms in Computational Geometry; Li; date
This is a survey paper of dynamic algorithms available for a variety of geometric problems, including nearest neighbor. For Voronoi diagrams, Li describes Mumuley's algorithm for diagrams of order 1 to \(\) in \(\) . Expected time for \(\) in a random \(\) -sequence is \(\) . For \(\) .
In the 2-dimensional case, the query time is \(\) and update time is \(\) . Similarly for 3-dimensions, query time is \(\) and update time is \(\) .
Mumuley. Computational Geometry: an introduction through randomized algorithms. 1994, Prentice-Hall Inc.
Improved Updating of Euclidean Distance Maps and Voronoi Diagrams; Lau, Sprunk, Burgard; date
Primarily focuses on the Generalized Voronoi Diagram as used in navigation for robotics. Diagrams are represented on grid maps.
Interactive analysis using voronoi diagrams: Algorithms to support dynamic update from a generic triangle-based data structure; Lee, Gahegan; 2002
Describe methods for updating five types of Voronoi diagrams using a data structure that stores the Delaunay triangulation of a given pointset. For Ordinary Vornoi Diagrams (OVD), edge swapping is used to dynamically insert points in \(\) time. To remove points, Ing's 1993 reversion algorithm is used, with worst case \(\) time.
Dynamic Voronoi Diagrams; Gowda, Kirkpatrick, Lee, Naamad; 1983
First note that dynamically updating a Voronoi diagram by adding or removing one point can change as many as \(\) edges in the worst case, therefore no worst-case-sublinear algorithms exist. They present an algorithm that is \(\) for both insert and delete, using a V-tree (Voronoi tree) design.
Each leaf of the tree stores a point in the given pointset \(\) . Internal nodes \(\) store the Voronoi diagram \(\) for the subtree rooted at \(\) . This requires \(\) storage, where \(\) is the height of the tree, but may be reduced to \(\) and preserving linear update time.
Consider the \(\) -minimum spanning circle problem: Given a planar point set \(\) where \(\) , find \(\) circles that every point in \(\) is contained in at least one circle and the largest circle is minimized.