Kinetic collision detection for two simple polygons

Written with Julien Basch, Leonidas J. Guibas, John Hershberger, and Li Zhang.
Computational Geometry: Theory and Applications 27(3):211-235, 2004.

Proceedings of the 10th Annual ACM­SIAM Symposium on Discrete Algorithms, 102-111, 1999.

We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called the external relative geodesic triangulation, which certifies their disjointness. We show how this subdivision can be maintained as a kinetic data structure when the polygons are moving, and analyze its performance in the kinetic setting.

Publications - Jeff Erickson ( 09 Apr 2004