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(n log 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 R(3), then we can detect collisions with a KDS of O(n log(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.
collision detection fat objects kinetic data structures