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

M.T. Berg, de; M.J.M. Roeloffzen; B. Speckmann

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

M.T. Berg, de, M.J.M. Roeloffzen, B. Speckmann

Algorithms

Research output: Contribution to conference › Abstract › Academic

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 language	English
Pages	53-56
Publication status	Published - 2012

Access to Document

publishers versionFinal published version, 134 KB

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

Berg, de, M. T., Roeloffzen, M. J. M., & Speckmann, B. (2012). Kinetic collision detection for low-density scenes in the black-box model. 53-56.

@conference{fa32d95fd524464abfde08eb57e8eb1e,

title = "Kinetic collision detection for low-density scenes in the black-box model",

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.",

author = "{Berg, de}, M.T. and M.J.M. Roeloffzen and B. Speckmann",

year = "2012",

language = "English",

pages = "53--56",

}

TY - CONF

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

AU - Berg, de, M.T.

AU - Roeloffzen, M.J.M.

AU - Speckmann, B.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Abstract

SP - 53

EP - 56

ER -