12:45 PM, October 26, 2000
Gates Building, Room 104

Kinetic Data Structures

Leonidas J. Guibas,
Computer Science Department,
Stanford University

About the talk:

Computer systems commonly cache the values of variables to gain efficiency. In applications where the goal is to track attributes of a continuously moving or deforming physical system over time, caching relations between variables works better than caching individual values. The reason is that, as the system evolves, such relationships are more stable than the values of individual variables.

Kinetic data structures (KDSs) are a novel formal framework for designing and analyzing sets of assertions to cache about the environment, so that these assertion sets are at once relatively stable and tailored to facilitate or trivialize the computation of the attribute of interest. Formally, a KDS is a mathematical proof animated through time, proving the validity of a certain computation for the attribute of interest. KDSs have rigorous associated measures of performance and their design shares many qualities with that of classical data structures.

The KDS framework has led to many new and promising algorithms in virtual reality applications. Among these are collision detection for moving rigid and deformable bodies, local environment tracking for moving agents, and visibility/occlusion maintenance. This talk will survey the general ideas behind KDSs and illustrate their application to geometric problems that arise in animation and physical simulation. Mobile network issues, such as connectivity and routing in ad-hoc networks, appear to be another area where KDS techniques can be usefully applied.

About the speaker:

Leonidas J. Guibas works on algorithms for sensing, modeling, reasoning, rendering, and acting on the physical world. His interests span computational geometry, geometric modeling, computer graphics, computer vision, robotics, and discrete algorithms. His current activities focus on animation, collision detection, efficient rendering, motion planning, and image data-bases. He heads the Geometric Computation group at Stanford University, where he is Professor of Computer Science.