Rice University
Department of Computer Science
presents

Leo Guibas

Professor of Computer Science
Stanford University

Kinetic Data Structures

Abstract
Suppose we are simulating a collection of continuously moving bodies, rigid or deformable, whose instantaneous motion follows known laws. As the simulation proceeds, we are interested in maintaining certain quantities of interest (for example, the separation of the closest pair of objects), or detecting certain discrete events (for example, collisions--which may alter the motion laws of the objects). In this talk we will present a general framework for addressing such problems and tools for designing and analyzing relevant algorithms, which we call kinetic data structures. The resulting techniques satisfy three desirable properties:
  1. they exploit the continuity of the motion of the objects to gain efficiency,
  2. the number of events processed by the algorithms is close to the minimum necessary in the worst case, and
  3. any object may change its 'flight plan' at any moment with a low cost update to the simulation data structures.
Friday, May 9, 1997 @ 2 p.m. in Duncan Hall 1070
Reception in Duncan Hall 3092 to follow