ABSTRACT
We present kinetic data structures for detecting col lisions between a set of polygons that are moving continuously in the plane. Unlike classical collisiondetection methods that rely on bounding volume hi erarchies, our method is based on deformable tilings of the free space surrounding the polygons. The ba sic shape of our tiles is that of a pseudo-triangle, a shape sufficiently flexible to allow extensive deforma tion, yet structured enough to make detection of self collisions easy. We show different schemes for main taining pseudo-triangulations using the framework of kinetic data structures, and analyze their performance. Specifically, we first describe an algorithm for main taining a pseudo-triangulation of a point set, and show that this pseudo-triangulation changes only quadratically many times if points move along algebraic arcs of constant degree. We then describe an algorithm for maintaining a pseudo-triangulation of a set of convex polygons. Finally, we extend our algorithm to the gen eral case of maintaining a pseudo-triangulation of a set of moving simple polygons. These methods can be ex tended to situations where the polygons deform as well as move.
