Kinetic Collision Detection for Convex Fat Objects

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are:

(i)

If the objects are 3-dimensional balls that roll on a plane, then we can detect collisions with a KDS of size O(nlog n) that can handle events in O(log 2 n) time. This structure processes O(n 2) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories.

(ii)

If the objects are convex fat 3-dimensional objects of constant complexity that are free-flying in ℝ3, then we can detect collisions with a KDS of O(nlog 6 n) size that can handle events in O(log 7 n) time. This structure processes O(n 2) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. If the objects have similar sizes then the size of the KDS becomes O(n) and events can be handled in O(log n) time.

M.A. and S.-H.P. were supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 612.065.307. M.d.B. was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.