Kinetic collision detection for balls rolling on a plane
Mohammad Ali Abam, Mark de Berg, SH Sheung-Hung Poon, Bettina Speckmann · TU/e Research Portal · 2006
This abstract presents a first step towards kinetic col- lision detection in 3 dimensions. In particular, we design a compact and responsive kinetic data struc- ture (KDS) for detecting collisions between n balls of arbitrary sizes rolling on a plane. The KDS has size O(n log n) and can handle events in O(log n) time. The structure processes O(n2) events in the worst case, assuming that the objects follow low-degree al- gebraic trajectories. The full paper [1] presents ad- ditional results for convex fat 3-dimensional objects that are free-flying in R3.