de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Fast algorithms for collision and proximity problems involving moving geometric objects

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44551

Gupta,  Prosenjit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.