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


Fast algorithms for collision and proximity problems involving moving geometric objects

Gupta, Prosenjit and Janardan, Janardan and Smid, Michiel

MPI-I-94-113. April 1994, 22 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
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-113.pdfMPI-I-94-113.pdfMPI-I-94-113.dvi.gz41 KBytes; 153 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:
Hide details for BibTeXBibTeX
  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},