Institute of
Discrete Mathematics and Geometry

Kinetic Data Structures (KDS) have now been around for about five or six years and have given rise to both theoretical and practical developments. This talk will provide a short introduction to KDS, illustrate the concept with a number of examples, and then focus on the more recent work in the field.

A KDS is an algorithmic tool for problems where the goal is to track an attribute of a continuously moving or deforming physical system over time. A KDS succintly summarizes the important aspects of the state of the system in a set of spatial relationships, called certificates, that facilitate or trivialize the computation of the attribute of interest. As the system evolves and certificates fail, a KDS repair mechanism is invoked to update the certificate set and the associated attribute computation. Good KDS design means selecting a certificate set that facilitates the attribute computation, yet is relatively stable and robust under object motion. KDSs have rigorous associated measures of performance and their design shares many qualities with that of classical data structures.

Originally the KDS framework led to new and promising algorithms in virtual reality applications, including collision detection and visibility computations. This talk will quickly survey this work and then focus on some of the newer developments, including applications to physical simulation and ad hoc communication and sensor networks.

http://geometry.stanford.edu/member/guibas/