## Abstract

Consider a set of geometric objects, such as points or axes-parallel hyper-rectangles 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. In particular, two open problems from the literature are solved: Deciding in o(n^{2}) time if there is a collision in a set of n moving points in IR^{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 language | English (US) |
---|---|

Title of host publication | Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings |

Editors | Jan van Leeuwen |

Publisher | Springer Verlag |

Pages | 278-289 |

Number of pages | 12 |

ISBN (Print) | 9783540584346 |

DOIs | |

State | Published - 1994 |

Event | 2nd Annual European Symposium on Algorithms, ESA 1994 - Utrecht, Netherlands Duration: Sep 26 1994 → Sep 28 1994 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 855 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 2nd Annual European Symposium on Algorithms, ESA 1994 |
---|---|

Country/Territory | Netherlands |

City | Utrecht |

Period | 9/26/94 → 9/28/94 |

### Bibliographical note

Funding Information:The research of these authors was supported in part by NSF grant CCRa-92-00270. This author was supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II).

Publisher Copyright:

© Springer-Verlag Berlin Heidelberg 1994.