Kinetic Maintenance of Proximity Structures

Li Zhang
Ph.D. thesis, Stanford Univ., Computer Science Dept., May 2000
http://www.hpl.hp.com/personal/Li_Zhang/papers/thesis.ps

Cites:

• Parametric and kinetic minimum spanning trees
• Dynamic algorithms for half-space reporting, proximity problems, and geometric minimum spanning trees
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Geometric lower bounds for parametric matroid optimization
• Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions
• Maintenance of a minimum spanning forest in a dynamic planar graph