##### 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.