MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Efficient collision detection for moving polyhedra

Schömer, Elmar and Thiel, Christian

September 1994, 24 pages.

Status: available - back from printing

In this paper we consider the following problem: given two general polyhedra of complexity $n$, one of which is moving translationally or rotating about a fixed axis, determine the first collision (if any) between them. We present an algorithm with running time $O(n^{8/5 + \epsilon})$ for the case of translational movements and running time $O(n^{5/3 + \epsilon})$ for rotational movements, where $\epsilon$ is an arbitrary positive constant. This is the first known algorithm with sub-quadratic running time.

  • Attachement: (88 KBytes); MPI-I-94-147.pdf (245 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Sch{\"o}mer, Elmar and Thiel, Christian},
  TITLE = {Efficient collision detection for moving polyhedra},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-147},
  MONTH = {September},
  YEAR = {1994},
  ISSN = {0946-011X},