Lower Bounds on the Complexity of Some Optimal Data Structures
From MaRDI portal
Publication:3902460
DOI10.1137/0210001zbMath0454.68006OpenAlexW2070228513MaRDI QIDQ3902460
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210001
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20)
Related Items
An algorithm for handling many relational calculus queries efficiently. ⋮ Lower bounds for off-line range searching ⋮ Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems ⋮ Tight lower bounds for halfspace range searching ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Lower bounds on zero-one matrices. ⋮ On the time-space complexity of reachability queries for preprocessed graphs ⋮ How hard is half-space range searching? ⋮ Lower Bounds on the Complexity of Polytope Range Searching ⋮ The effect of corners on the complexity of approximate range searching ⋮ New lower bounds for Hopcroft's problem ⋮ A New Lower Bound for Semigroup Orthogonal Range Searching ⋮ Quasi-optimal range searching in spaces of finite VC-dimension ⋮ Unnamed Item ⋮ An application of $m$-ary trees to the design of data structures for geometric searching problems ⋮ Inherent complexity trade-offs for range query problems ⋮ Lower bounds for dynamic algebraic problems ⋮ Query time versus redundancy trade-offs for range queries
