Thursday, April 9, 1998
3:00 PM (refreshments 2:45)
Room NE43-518
EECS Special Seminar
Abstract
Modeling the physical world in the computer raises problems that combine discrete and continuous features. For example, physical objects move along continuous trajectories; yet every so often discrete events occur, such as collisions between objects.
In a model of objects in space, there are many discrete attributes of interest: the minimum-distance pair, the convex hull, the minimum spanning tree, etc. When the objects are in motion, the values of these attributes change, and it becomes necessary to keep track of them over time.
In this talk, I introduce a framework for handling this type of problem. I define a new type of data structure, called a "kinetic data structure," for the maintenance of discrete attributes of moving objects. The techniques are illustrated with two examples: maintenance of the convex hull of moving points in the plane, and of the minimum-distance pair.
This is joint work with Leo Guibas and John Hershberger.
|
Modified: Apr 1, 1998|
Current events|
Your comments
and inquiries are welcome.