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.
Download:
|