Kinetic collision detection for low-density scenes in the black-box model

Research output: Contribution to conferenceAbstractAcademic

33 Downloads (Pure)

Abstract

We present an efficient method for collision detection in the black-box KDS model for a set S of n objects in the plane. In this model we receive the object locations at regular time steps and we know a bound dmax on the maximum displacement of any object within one time step. Our method maintains, in O((¿+k)n) time per time step, a compressed quadtree on the bounding-box vertices of the objects; here ¿ denotes the density of S and k denotes the maximum number of objects that can intersect any disk of radius dmax. Collisions can then be detected by testing O((¿+k)2n) pairs of objects for intersection.
Original languageEnglish
Pages53-56
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'Kinetic collision detection for low-density scenes in the black-box model'. Together they form a unique fingerprint.

  • Cite this