Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Efficient collision detection for moving polyhedra

Schömer, Elmar and Thiel, Christian

MPI-I-94-147. September 1994, 24 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s): KBytes; 245 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
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},