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 ACMSIAM Symposium on Discrete Algorithms, 102-111, 1999.

Official journal version from ScienceDirect (subscription or payment required)
Download SODA version (© 1998 SIAM):
Download abstract from the 3rd CGC Workshop on Computational Geometry:
Official SODA version from ACM's Digital Library (subscription or $5 payment required)
See also: Separationsensitive collision detection for convex objects

Abstract:

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 (jeffe@cs.uiuc.edu) 09 Apr 2004