# Item

ITEM ACTIONSEXPORT

Released

Report

#### Fast algorithms for collision and proximity problems involving moving geometric objects

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-94-113.pdf

(Any fulltext), 154KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Gupta, P., Janardan, J., & Smid, M.(1994). *Fast algorithms
for collision and proximity problems involving moving geometric objects* (MPI-I-94-113). Saarbrücken: Max-Planck-Institut
für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B50E-D

##### Abstract

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.