DOI

We introduce dynamic smooth (a.k.a. balanced) compressed quadtrees with worst-case constant time updates in constant dimensions. We distinguish two versions of the problem. First, we show that quadtrees as a space-division data structure can be made smooth and dynamic subject to split and merge operations on the quadtree cells. Second, we show that quadtrees used to store a set of points in ℝd can be made smooth and dynamic subject to insertions and deletions of points. The second version uses the first but must additionally deal with compression and alignment of quadtree components. In both cases our updates take 2O(dlogd) time, except for the point location part in the second version which has a lower bound of Ω(logn); but if a pointer (finger) to the correct quadtree cell is given, the rest of the updates take worst-case constant time. Our result implies that several classic and recent results (ranging from ray tracing to planar point location) in computational geometry which use quadtrees can deal with arbitrary point sets on a real RAM pointer machine.

Язык оригиналаанглийский
Название основной публикации34th International Symposium on Computational Geometry, SoCG 2018
РедакторыCsaba D. Toth, Bettina Speckmann
ИздательSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Страницы45:1-45:15
Число страниц15
Том99
ISBN (электронное издание)9783959770668
DOI
СостояниеОпубликовано - 1 июн 2018
Опубликовано для внешнего пользованияДа
Событие34th International Symposium on Computational Geometry, SoCG 2018 - Budapest, Венгрия
Продолжительность: 11 июн 201814 июн 2018

конференция

конференция34th International Symposium on Computational Geometry, SoCG 2018
Страна/TерриторияВенгрия
ГородBudapest
Период11/06/1814/06/18

    Предметные области Scopus

  • Программный продукт

ID: 38614052