Dynamic smooth compressed quadtrees

DOI10.4230/LIPICS.SOCG.2018.45MaRDI QIDQ5115813zbMATH OpenOpenAlexFDO

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

Publication date 18 August 2020

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

zbMATH Keywords

quadtreealignmentcompressionreal RAMsmooth dynamic data structure

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1222814 (Why is no real title available?)
• scientific article; zbMATH DE number 1156715 (Why is no real title available?)
• scientific article; zbMATH DE number 6876073 (Why is no real title available?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A self-adjusting data structure for multidimensional point sets
• Amortized analysis of smooth quadtrees in all dimensions
• Computational geometry. Algorithms and applications.
• Cost prediction for ray shooting in octrees
• Delaunay triangulations in O (sort( n )) time and more
• Dynamic planar point location with sub-logarithmic local updates
• Dynamic smooth compressed quadtrees
• Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals
• Fully dynamic Delaunay triangulation in logarithmic expected per operation
• Geometric approximation algorithms
• Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes
• Minimum Spanning Trees in k-Dimensional Space
• Neighbor finding techniques for images represented by quadtrees
• PARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS
• Provably good mesh generation
• Quad trees: A data structure for retrieval by composite keys
• SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
• Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent

Cited in

(4)

• Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes
• 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)