hide
Free keywords:
-
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.
