Standard

Dynamic smooth compressed quadtrees. / Ivor Hoog, V. D.; Khramtcova, Elena; Löffler, Maarten.

34th International Symposium on Computational Geometry, SoCG 2018. ed. / Csaba D. Toth; Bettina Speckmann. Vol. 99 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. p. 45:1-45:15.

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

Harvard

Ivor Hoog, VD, Khramtcova, E & Löffler, M 2018, Dynamic smooth compressed quadtrees. in CD Toth & B Speckmann (eds), 34th International Symposium on Computational Geometry, SoCG 2018. vol. 99, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 45:1-45:15, 34th International Symposium on Computational Geometry, SoCG 2018, Budapest, Hungary, 11/06/18. https://doi.org/10.4230/LIPIcs.SoCG.2018.45

APA

Ivor Hoog, V. D., Khramtcova, E., & Löffler, M. (2018). Dynamic smooth compressed quadtrees. In C. D. Toth, & B. Speckmann (Eds.), 34th International Symposium on Computational Geometry, SoCG 2018 (Vol. 99, pp. 45:1-45:15). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2018.45

Vancouver

Ivor Hoog VD, Khramtcova E, Löffler M. Dynamic smooth compressed quadtrees. In Toth CD, Speckmann B, editors, 34th International Symposium on Computational Geometry, SoCG 2018. Vol. 99. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. p. 45:1-45:15 https://doi.org/10.4230/LIPIcs.SoCG.2018.45

Author

Ivor Hoog, V. D. ; Khramtcova, Elena ; Löffler, Maarten. / Dynamic smooth compressed quadtrees. 34th International Symposium on Computational Geometry, SoCG 2018. editor / Csaba D. Toth ; Bettina Speckmann. Vol. 99 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. pp. 45:1-45:15

BibTeX

@inproceedings{25dca44d2e0a42f19e79e2c9157ccc4c,
title = "Dynamic smooth compressed quadtrees",
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 ℝ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.",
keywords = "Alignment, Compression, Data structure, Dynamic, Quadtree, Real ram, Smooth",
author = "{Ivor Hoog}, {V. D.} and Elena Khramtcova and Maarten L{\"o}ffler",
year = "2018",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2018.45",
language = "English",
volume = "99",
pages = "45:1--45:15",
editor = "Toth, {Csaba D.} and Bettina Speckmann",
booktitle = "34th International Symposium on Computational Geometry, SoCG 2018",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
address = "Germany",
note = "34th International Symposium on Computational Geometry, SoCG 2018 ; Conference date: 11-06-2018 Through 14-06-2018",

}

RIS

TY - GEN

T1 - Dynamic smooth compressed quadtrees

AU - Ivor Hoog, V. D.

AU - Khramtcova, Elena

AU - Löffler, Maarten

PY - 2018/6/1

Y1 - 2018/6/1

N2 - 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.

AB - 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.

KW - Alignment

KW - Compression

KW - Data structure

KW - Dynamic

KW - Quadtree

KW - Real ram

KW - Smooth

UR - http://www.scopus.com/inward/record.url?scp=85048954481&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2018.45

DO - 10.4230/LIPIcs.SoCG.2018.45

M3 - Conference contribution

AN - SCOPUS:85048954481

VL - 99

SP - 45:1-45:15

BT - 34th International Symposium on Computational Geometry, SoCG 2018

A2 - Toth, Csaba D.

A2 - Speckmann, Bettina

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 34th International Symposium on Computational Geometry, SoCG 2018

Y2 - 11 June 2018 through 14 June 2018

ER -

ID: 38614052