Dynamic smooth compressed quadtrees

DOI10.4230/LIPICS.SOCG.2018.45zbMATH Open1489.68064arXiv1712.05591OpenAlexW2799206828MaRDI QIDQ5115813FDOQ5115813

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

Publication date: 18 August 2020

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 $mathbb{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^{mathcalO(dlogd)}$ time, except for the point location part in the second version which has a lower bound of $Theta(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.

Full work available at URL: https://arxiv.org/abs/1712.05591

Recommendations

• Amortized Analysis of Smooth Quadtrees in All Dimensions
• Faster compressed quadtrees
• Amortized analysis of smooth quadtrees in all dimensions
• Quad-\(k\mathrm d\) trees: a general framework for \(k\mathrm d\) trees and quad trees
• Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes

zbMATH Keywords

quadtreealignmentcompressionreal RAMsmooth dynamic data structure

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Quad trees: A data structure for retrieval by composite keys
• Computational geometry. Algorithms and applications.
• Provably good mesh generation
• Title not available (Why is that?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Delaunay triangulations in O (sort( n )) time and more
• Minimum Spanning Trees in k-Dimensional Space
• PARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS
• Amortized analysis of smooth quadtrees in all dimensions
• Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes
• SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
• Fully dynamic Delaunay triangulation in logarithmic expected per operation
• Neighbor finding techniques for images represented by quadtrees
• Dynamic Planar Point Location with Sub-logarithmic Local Updates
• A Self-adjusting Data Structure for Multidimensional Point Sets
• Cost prediction for ray shooting in octrees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent
• Dynamic smooth compressed quadtrees
• Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals
• Title not available (Why is that?)

Cited In (3)

• Dynamic smooth compressed quadtrees
• Faster compressed quadtrees
• Preprocessing Ambiguous Imprecise Points

This page was built for publication: Dynamic smooth compressed quadtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115813)