MPI-I-94-147
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.
-
MPI-I-94-147.pdf
- Attachement: MPI-I-94-147.ps.gz (88 KBytes); MPI-I-94-147.pdf (245 KBytes)
URL to this document: https://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},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-94-147},
MONTH = {September},
YEAR = {1994},
ISSN = {0946-011X},
}