ABSTRACT
Suppose we are simulating a collection of continu ously moving bodies, rigid or deformable, whose in stantaneous motion follows known laws. As the sim ulation proceeds, we are interested in maintaining cer tain quantities of interest (for example, the separation of the closest pair of objects), or detecting certain dis crete events (for example, collisions) which may, in turn, alter the motion laws of the objects. In this paper we present a general framework for addressing such problems and the tools for designing and analyzing relevant algorithms, which we call kinetic data struc tures. We discuss kinetic data structures for a va riety of fundamental geometric problems, such as the maintenance of convex hulls, Voronoi and Delaunay diagrams, closest pairs, and intersection and visibil ity problems. We also briefly address the issues that arise in implementing such structures robustly and ef ficiently. The resulting techniques satisfy three desir able properties: (1) they exploit the continuity of the motion of the objects to gain efficiency, (2) the num ber of events processed by the algorithms is close to the minimum necessary in the worst case, and (3) any ob ject may change its flight plan’ at any moment with a low cost update to the simulation data structures. For computer applications dealing with motion in the phys ical world, kinetic data structures lead to simulation performance unattainable by other means. In addition, they raise fundamentally new combinatorial and algo rithmic questions whose study may prove fruitful for other disciplines as well.
