@inproceedings{a7fb1e77c7b04874aa191cc648ba79f6,
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 ℝ3, then we can detect collisions with a KDS of O(n log 6 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 = "Abam, {M. A.} and {De Berg}, M. and Poon, {S. H.} and B. Speckmann",
year = "2006",
doi = "10.1007/11841036_4",
language = "English",
isbn = "3540388753",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "4--15",
booktitle = "Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings",
address = "Germany",
note = "14th Annual European Symposium on Algorithms, ESA 2006 ; Conference date: 11-09-2006 Through 13-09-2006",
}