##
Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision

### Kinetic Data Structures

Leonidas J. Guibas

Department of Computer Science

Stanford University

Monday, Oct 9, 2000, 4:15PM

TCseq200, Lecture Hall A

`http://robotics.stanford.edu/ba-colloquium/`

#### Abstract

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

`bac-coordinators@cs.stanford.edu`
Back to the Colloquium Page

Last modified: Wed Sep 27 14:55:02 PST 2000