Kinetic collision detection for convex fat objects

M.A. Abam, M. Berg, de, S.H. Poon, B. Speckmann

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2006 (Proceedings 14th Annual European Symposium, Zürich, Switzerland, September 11-13, 2006)
EditorsY. Azar, T. Erlebach
Place of PublicationBerlin
PublisherSpringer
Pages4-15
ISBN (Print)3-540-38875-3
DOIs
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
Volume4168
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Kinetic collision detection for convex fat objects'. Together they form a unique fingerprint.

Cite this