Kinetic Collision Detection for Convex Fat Objects
Mohammad Ali Abam, Mark de Berg, Sheung-Hung Poon, Bettina Speckmann · Algorithmica · 2007
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: 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. 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 ( 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.