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

MPI-I-94-147

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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-94-147.pdfMPI-I-94-147.pdfMPI-I-94-147.ps.gz88 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: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-147
Hide details for BibTeXBibTeX
@TECHREPORT{SchoernerThiel94,
  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},
}