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

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

35 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's53-56
StatusGepubliceerd - 2012

Vingerafdruk Duik in de onderzoeksthema's van 'Kinetic collision detection for low-density scenes in the black-box model'. Samen vormen ze een unieke vingerafdruk.

Citeer dit