@inproceedings{c8532000e604466dba8680dfa6d68414,

title = "Kinetic collision detection for convex fat objects",

abstract = "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 n) time. This structure processes O(n2) 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 R3, then we can detect collisions with a KDS of O(n log6 n) size that can handle events in O(log6 n) time. This structure processes O(n2) 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(1) time.",

author = "M.A. Abam and {Berg, de}, M. and S.H. Poon and B. Speckmann",

year = "2006",

doi = "10.1007/11841036_4",

language = "English",

isbn = "3-540-38875-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "4--15",

editor = "Y. Azar and T. Erlebach",

booktitle = "Algorithms - ESA 2006 (Proceedings 14th Annual European Symposium, Z{\"u}rich, Switzerland, September 11-13, 2006)",

address = "Germany",

}