Kinetic collision detection between two simple polygons

Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)211-235
Number of pages25
JournalComputational Geometry: Theory and Applications
Issue number3
StatePublished - Mar 2004


  • Collision detection
  • Geodesic triangulation
  • Kinetic data structures

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Kinetic collision detection between two simple polygons'. Together they form a unique fingerprint.

Cite this