Weller, ReneFrese, UdoZachmann, GabrielJan Bender and Jeremie Dequidt and Christian Duriez and Gabriel Zachmann2014-02-062014-02-062013978-3-905674-57-6https://doi.org/10.2312/PE.vriphys.vriphys13.061-070We prove that the maximum number of intersecting pairs spheres between two sets of polydisperse sphere packings is linear in the worst case. This observation is the basis for a new collision detection algorithm. Our new approach guarantees a linear worst case running time for arbitrary 3D objects. Additionally, we present a parallelization of our new algorithm that runs in constant time, even in the worst case. Consequently, it is perfectly suited for all time-critical environments that allow only a fixed time budget for finding collision. Our implementation using CUDA shows collision detection at haptic rates for complex objects.I.3.5 [Computer Graphics]Computational Geometry and Object ModelingGeometric algorithms