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)


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
ISBN (Print)978-3-642-33089-6
Publication statusPublished - 2012
Event20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenia
Duration: 10 Sep 201212 Sep 2012
Conference number: 20

Publication series

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


Conference20th Annual European Symposium on Algorithms (ESA 2012)
Abbreviated titleESA 2012
Internet address

Cite this