Kinetic collision detection for convex fat objects

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

Research output: Chapter in Book/Conference proceedingConference contributionpeer-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 ℝ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.

Original languageEnglish
Title of host publicationAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages4-15
Number of pages12
ISBN (Print)3540388753, 9783540388753
DOIs
Publication statusPublished - 2006
Externally publishedYes
Event14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland
Duration: 11 Sept 200613 Sept 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th Annual European Symposium on Algorithms, ESA 2006
Country/TerritorySwitzerland
CityZurich
Period11/09/0613/09/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this