Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

Abstract

We present an efficient method for maintaining a compressed quadtree for a set of moving points in R d . Our method works in the black-box KDS model, where we receive the locations of the points at regular time steps and we know a bound d max on the maximum displacement of any point within one time step. When the number of points within any ball of radius d max is at most k at any time, then our update algorithm runs in O(nlogk) time. We generalize this result to constant-complexity moving objects in R d . The compressed quadtree we maintain has size O(n); under similar conditions as for the case of moving points it can be maintained in O(n log¿) time per time step, where ¿ is the density of the set of objects. The compressed quadtree can be used to perform broad-phase collision detection for moving objects; it will report in O((¿¿+¿k)n) time a superset of all intersecting pairs of objects.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2012 (20th European Symposium on Algorithms, Ljubljana, Slovenia, September 10-12, 2012. Proceedings)
EditorsL. Epstein, P. Ferragina
Place of PublicationBerlin
PublisherSpringer
Pages383-394
ISBN (Print)978-3-642-33089-6
DOIs
Publication statusPublished - 2012
Event20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenia
Duration: 10 Sep 201212 Sep 2012
Conference number: 20
http://link.springer.com/book/10.1007/978-3-642-33090-2
http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2012.html

Publication series

NameLecture Notes in Computer Science
Volume7501
ISSN (Print)0302-9743

Conference

Conference20th Annual European Symposium on Algorithms (ESA 2012)
Abbreviated titleESA 2012
CountrySlovenia
CityLjubljana
Period10/09/1212/09/12
Internet address

Cite this

Berg, de, M. T., Roeloffzen, M. J. M., & Speckmann, B. (2012). Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes. In L. Epstein, & P. Ferragina (Eds.), Algorithms - ESA 2012 (20th European Symposium on Algorithms, Ljubljana, Slovenia, September 10-12, 2012. Proceedings) (pp. 383-394). (Lecture Notes in Computer Science; Vol. 7501). Springer. https://doi.org/10.1007/978-3-642-33090-2_34