Proximity Problems on Moving Points

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 dimensions: 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. 1 Introduction The goal of this paper is to address a number of proximity problems for points and balls moving continuously in R d . Examples of such problems are the maintenance of the closest pair and the minimum spanning tree (MST) of the moving objects. In the dynamic simulation of virtual environments, collision detection between the moving objects is frequently important. Complex bodies can be approximated by bounding spheres and knowledge of the closest pair of these sphere..