Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees

DOI10.1007/BF00263763zbMath0349.68016OpenAlexW2030116982WikidataQ55920347 ScholiaQ55920347MaRDI QIDQ1235007

K. Appert

Publication date: 1977

Published in: Acta Informatica (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

An algorithm for handling many relational calculus queries efficiently. ⋮ A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids ⋮ K-d tree based approach for point location problem in explicit model predictive control ⋮ Fast model predictive control combining offline method and online optimization with K-D tree ⋮ Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems ⋮ Dynamic orthogonal range queries in OLAP. ⋮ A Measure-Theoretic Interpretation of Sample Based Numerical Integration with Applications to Inverse and Prediction Problems under Uncertainty ⋮ The extendible cell method for closest point problems ⋮ Information storage and search complexity theory ⋮ A greedy clustering algorithm based on interval pattern concepts and the problem of optimal box positioning ⋮ A kd-tree-accelerated hybrid data-driven/model-based approach for poroelasticity problems with multi-fidelity multi-physics data ⋮ Optimal binary search trees ⋮ Index structures for fast similarity search for real vectors. II ⋮ Average case analysis of region search in balanced k-d trees ⋮ Ranked document selection ⋮ An application of $m$-ary trees to the design of data structures for geometric searching problems ⋮ An improved algorithm for the maximum agreement subtree problem ⋮ Chaining algorithms for multiple genome comparison ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry