DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2018.45

Dynamic Smooth Compressed Quadtrees

Authors: Ivor van der Hoog, Elena Khramtcova, and Maarten Löffler

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract

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 R^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 2^{O(d log d)} time, except for the point location part in the second version which has a lower bound of Omega(log n); 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.

Cite as

Ivor van der Hoog, Elena Khramtcova, and Maarten Löffler. Dynamic Smooth Compressed Quadtrees. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2018.45,
  author =	{van der Hoog, Ivor and Khramtcova, Elena and L\"{o}ffler, Maarten},
  title =	{{Dynamic Smooth Compressed Quadtrees}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.45},
  URN =		{urn:nbn:de:0030-drops-87581},
  doi =		{10.4230/LIPIcs.SoCG.2018.45},
  annote =	{Keywords: smooth, dynamic, data structure, quadtree, compression, alignment, Real RAM}
}

Search Results

Documents authored by Khramtcova, Elena

Dynamic Smooth Compressed Quadtrees

Abstract

Cite as

Thanks for your feedback!

Could not send message