MPI-I-94-113
Fast algorithms for collision and proximity problems involving moving geometric objects
Gupta, Prosenjit and Janardan, Janardan and Smid, Michiel
April 1994, 22 pages.
.
Status: available - back from printing
Consider a set of geometric objects, such as points, line
segments, or axes-parallel hyperrectangles in $\IR^d$, that
move with constant but possibly different velocities along
linear trajectories. Efficient algorithms are presented for
several problems defined on such objects, such as determining
whether any two objects ever collide and computing the minimum
inter-point separation or minimum diameter that ever occurs.
The strategy used involves reducing the given
problem on moving objects to a different
problem on a set of static objects, and then
solving the latter problem using
techniques based on sweeping, orthogonal range
searching, simplex composition, and parametric search.
-
MPI-I-94-113.pdf
- Attachement: MPI-I-94-113.dvi.gz (41 KBytes); MPI-I-94-113.pdf (153 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-113
BibTeX
@TECHREPORT{GuptaJanardanSmid94,
AUTHOR = {Gupta, Prosenjit and Janardan, Janardan and Smid, Michiel},
TITLE = {Fast algorithms for collision and proximity problems involving moving geometric objects},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-94-113},
MONTH = {April},
YEAR = {1994},
ISSN = {0946-011X},
}