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.