Kinetic collision detection between two simple polygons

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

Research output: Contribution to conferencePaperpeer-review

Abstract

We design a kinetic data structure for detecting collisions between to 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)
Pages102-111
Number of pages10
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

Cite this