Kinetic Data Structures

Modeling the physical world in the computer raises problems that intertwine discrete and continuous aspects. For example, physical objects move along continuous trajectories; yet every so often discrete events occur, such as collisions between objects. In a model of objects in space, there are many discrete attributes that one may want to compute: the closest pair, the convex hull, the minimum spanning tree, etc. When the objects are in motion, the values of these attributes change over time, and it becomes necessary to keep track of them as the objects move. In this thesis, we introduce a general approach, and an analysis framework, for solving this type of problems. To keep track of a discrete attribute, we create a new type of data structure, called a kinetic data structure. A kinetic data structure is made of a proof of correctness of the attribute which is animated through time by a discrete event simulation.