Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Kinetic Collision Detection for Convex Fat Objects
verfasst von : M. A. Abam, M. de Berg, S. -H. Poon, B. Speckmann
Erschienen in: Algorithms – ESA 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
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
${\mathbb R}^3$
, then we can detect collisions with a KDS of
O
(
n
log
6
n
) size that can handle events in
O
(log
6
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
(1) time.