Divided \(k-d\) trees

DOI10.1007/BF01759075zbMath0745.68057OpenAlexW1530943085MaRDI QIDQ1180539

Mark H. Overmars, Marc J. van Kreveld

Publication date: 27 June 1992

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01759075

zbMATH Keywords

range queriesdynamic data structurequad-tree\(k-d\)-tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

Efficient dynamic range searching using data replication ⋮ Efficient splitting and merging algorithms for order decomposable problems ⋮ Median and hybrid median \(K\)-dimensional trees ⋮ Space efficient dynamic orthogonal range reporting ⋮ Orthogonal range searching in linear and almost-linear space ⋮ A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES ⋮ Efficient splitting and merging algorithms for order decomposable problems.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• Worst-case optimal insertion and deletion methods for decomposable searching problems
• Dynamic multi-dimensional data structures based on quad- and k-d trees
• Decomposable searching problems
• Concatenable structures for decomposable problems
• Quad trees: A data structure for retrieval by composite keys
• Adding range restriction capability to dynamic data structures
• Multidimensional binary search trees used for associative searching
• Multidimensional Binary Search Trees in Database Applications