Proximity problems on moving points
Julien Basch, Leonidas Guibas, Li Zhang · 1997
A kinetic data structure for the maintenance of a multidimensional range search tree is introduced.This structure is used as a building block to obtain kinetic data structures for two classical geometric proximity problems in arbitrary dlmensions: the first structure maintains the closest pair of a set of continuously moving points, and is provably efficient.The second structure maintains a spanning tree of the moving points whose cost remains within some prescribed factor of the minimum spanning tree.