max planck institut
informatik

# 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:

MPI-I-94-147.pdf88 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
BibTeX
@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},