Kinetic collision detection for convex fat objects

Mohammad Ali Abam, Mark De Berg, Sheung Hung Poon, Bettina Speckmann

Research output: Journal PublicationArticlepeer-review

5 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(nlog∈n) that can handle events in O(log∈ 2 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 ℝ 3, then we can detect collisions with a KDS of O(nlog∈ 6 n) size that can handle events in O(log∈ 7 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(log∈n) time.

Original languageEnglish
Pages (from-to)457-473
Number of pages17
JournalAlgorithmica
Volume53
Issue number4
DOIs
Publication statusPublished - Apr 2009
Externally publishedYes

Keywords

  • Collision detection
  • Fat objects
  • Kinetic data structures

ASJC Scopus subject areas

  • Computer Science (all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

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

Cite this