Document Open Access Logo

Dynamic Smooth Compressed Quadtrees

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.45.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Ivor van der Hoog
Elena Khramtcova
Maarten Löffler

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.SoCG.2018.45

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.
Keywords
  • smooth
  • dynamic
  • data structure
  • quadtree
  • compression
  • alignment
  • Real RAM

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Boris Aronov, Hervé Brönnimann, Allen Y Chang, and Yi-Jen Chiang. Cost prediction for ray shooting in octrees. Computational Geometry, 34(3):159-181, 2006. Google Scholar
  2. Huck Bennett, Evanthia Papadopoulou, and Chee Yap. Planar minimization diagrams via subdivision with applications to anisotropic Voronoi diagrams. Comput. Graph. Forum, 35(5):229-247, 2016. Google Scholar
  3. Huck Bennett and Chee Yap. Amortized analysis of smooth quadtrees in all dimensions. Computational Geometry, 63:20-39, 2017. Google Scholar
  4. Marshall Bern, David Eppstein, and John Gilbert. Provably good mesh generation. Journal on Computational System Sciences, 48(3):384-409, 1994. Google Scholar
  5. Marshall Bern, David Eppstein, and Shang-Hua Teng. Parallel construction of quadtrees and quality triangulations. International Journal on Computational Geometry and Applications, 9(6):517-532, 1999. Google Scholar
  6. Kevin Buchin and Wolfgang Mulzer. Delaunay triangulations in O(sort(n)) time and more. Journal of the ACM, 58(2):Art. 6, 2011. Google Scholar
  7. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67-90, 1995. Google Scholar
  8. Mark De Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, 2008. Google Scholar
  9. Mark De Berg, Marcel Roeloffzen, and Bettina Speckmann. Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes. Algorithms-ESA 2012, pages 383-394, 2012. Google Scholar
  10. Olivier Devillers, Stefan Meiser, and Monique Teillaud. Fully dynamic delaunay triangulation in logarithmic expected time per operation. Computational Geometry, 2(2):55-80, 1992. Google Scholar
  11. David Eppstein, Michael Goodrich, and Jonathan Sun. The skip quadtree: a simple dynamic data structure for multidimensional data. International Journal on Computational Geometry and Applications, 18(1-2):131-160, 2008. Google Scholar
  12. Raphael A. Finkel and Jon Louis Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Inform., 4:1-9, 1974. Google Scholar
  13. Sariel Har-Peled. Geometric approximation algorithms, volume 173. American mathematical society Boston, 2011. Google Scholar
  14. Ivor Hoog v.d., Elena Khramtcova, and Maarten Löffler. Dynamic smooth compressed quadtrees. arXiv preprint arXiv:1712.05591, 2017. Google Scholar
  15. Elena Khramtcova and Maarten Löffler. Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals. In Proc. 12th Int. Computer Science Symp. in Russia, (CSR), pages 176-190, 2017. Google Scholar
  16. S Rao Kosaraju and Mihai Pop. De-amortization of algorithms. In International Computing and Combinatorics Conference, pages 4-14. Springer, 1998. Google Scholar
  17. Drago Krznaric and Christos Levcopoulos. Computing a threaded quadtree from the Delaunay triangulation in linear time. Nordic Journal on Computating, 5(1):1-18, 1998. Google Scholar
  18. Maarten Löffler and Wolfgang Mulzer. Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent. SIAM Journal on Computing, 41(4):941-974, 2012. Google Scholar
  19. Maarten Löffler, Joseph A. Simons, and Darren Strash. Dynamic planar point location with sub-logarithmic local updates. In 13th Int. Symp. Algorithms and Data Structures (WADS), pages 499-511. Springer Berlin Heidelberg, 2013. full version: arXiv preprint arXiv:1204.4714. Google Scholar
  20. J David MacDonald and Kellogg S Booth. Heuristics for ray tracing using space subdivision. The Visual Computer, 6(3):153-166, 1990. Google Scholar
  21. Johannes Mezger, Stefan Kimmerle, and Olaf Etzmuß. Hierarchical techniques in collision detection for cloth animation. In Proc. Int. Conf. in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), 2003. Google Scholar
  22. Eunhui Park and David Mount. A self-adjusting data structure for multidimensional point sets. Algorithms-ESA 2012, pages 778-789, 2012. Google Scholar
  23. Hanan Samet. Neighbor finding techniques for images represented by quadtrees. Computer graphics and image processing, 18(1):37-57, 1982. Google Scholar
  24. Hanan Samet. The design and analysis of spatial data structures. Addison-Wesley, Boston, MA, USA, 1990. Google Scholar
  25. A Unnikrishnan, Priti Shankar, and YV Venkatesh. Threaded linear hierarchical quadtrees for computation of geometric properties of binary images. IEEE transactions on software engineering, 14(5):659-665, 1988. Google Scholar
  26. Pravin M. Vaidya. Minimum spanning trees in k-dimensional space. SIAM J. Comput., 17(3):572-582, 1988. URL: http://dx.doi.org/10.1137/0217035.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact