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


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.
Back to the Colloquium Page
Last modified: Wed Sep 27 14:55:02 PST 2000