### 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 language | English |
---|---|

Title of host publication | Algorithms - ESA 2012 (20th European Symposium on Algorithms, Ljubljana, Slovenia, September 10-12, 2012. Proceedings) |

Editors | L. Epstein, P. Ferragina |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 383-394 |

ISBN (Print) | 978-3-642-33089-6 |

DOIs | |

Publication status | Published - 2012 |

Event | 20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenia Duration: 10 Sep 2012 → 12 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

Name | Lecture Notes in Computer Science |
---|---|

Volume | 7501 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 20th Annual European Symposium on Algorithms (ESA 2012) |
---|---|

Abbreviated title | ESA 2012 |

Country | Slovenia |

City | Ljubljana |

Period | 10/09/12 → 12/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