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  presents ad- ditional results for convex fat 3-dimensional objects that are free-flying in R3.
|Publication status||Published - 2006|
|Event||22nd European Workshop on Computational Geometry (EuroCG 2006) - Delphi, Greece|
Duration: 27 Mar 2006 → 29 Mar 2006
Conference number: 22
|Workshop||22nd European Workshop on Computational Geometry (EuroCG 2006)|
|Period||27/03/06 → 29/03/06|