Tuesday, May 5, 1998
4:00 PM (refreshments 3:45)
Room NE43-941
EECS Special Seminar
Abstract
Collision detection is a fundamental geometric problem with numerous applications in areas such as computer graphics, robotics, computer aided design and manufacturing, and molecular modeling. I will describe a sequence of simple hierarchical data structures that allows us to efficiently detect collisions among a set of continuously moving objects, using a mixture of spatial partitioning and approximation techniques. We have developed and analyzed these structures in the kinetic data structure framework recently introduced by Basch, Guibas, and Hershberger. Our kinetic analysis provides much stronger theoretical guarantees than previous methods. For each data structure, combinatorial changes caused by the motion of the objects are easy to detect, and the data structures can be updated quickly after each change. The performance of our data structures provably adapts to geometric properties of the objects such as their relative sizes, distances, and aspect ratios.
The talk includes ongoing joint work with Pankaj Agarwal, Leo Guibas, John Hershberger, and Li Zhang.
|
Modified: Apr 23, 1998|
Current events|
Your comments
and inquiries are welcome.