Fast algorithms for collision and proximity problems involving moving geometric objects

Prosenjit Gupta, Ravi Janardan, Michiel Smid

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

Consider a set of geometric objects, such as points, line segments, or axes-parallel hyperrectangles in ℝ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 interpoint separation or minimum diameter that ever occurs. In particular, two open problems from the literature are solved: deciding in o(n2) time if there is a collision in a set of n moving points in ℝ2, where the points move at constant but possibly different velocities, and the analogous problem for detecting a red-blue collision between sets of red and blue moving points. 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.

Original languageEnglish (US)
Pages (from-to)371-391
Number of pages21
JournalComputational Geometry: Theory and Applications
Volume6
Issue number6
DOIs
StatePublished - Nov 1996

Bibliographical note

Funding Information:
’ The research was supported in part by NSF grant CCR-92-00270. E-mail: {pgupta,janardan}@cs.umn.edu. ‘Supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II). E-mail: michiel@mpi-sb.mpg.de.

Fingerprint

Dive into the research topics of 'Fast algorithms for collision and proximity problems involving moving geometric objects'. Together they form a unique fingerprint.

Cite this