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 \(k\) in \(R^d\) . Expected time for \(d=2\) in a random \((N,\delta)\) -sequence is \(O(k^2 + \log n)\) . For \(d > 2, O(k^{\lceil d/2\rceil + 2} n^{\lceil d/2 \rceil -1})\) .

In the 2-dimensional case, the query time is \(O(k \log^2 n)\) and update time is \(O(k^2 + \log n)\) . Similarly for 3-dimensions, query time is \(O(k \log^2 n)\) and update time is \(O(k^4 n \log^2 n)\) .

Mumuley. Computational Geometry: an introduction through randomized algorithms. 1994, Prentice-Hall Inc.