A Lower Bound on the Complexity of Orthogonal Range Queries
From MaRDI portal
Publication:3922168
DOI10.1145/322276.322281zbMath0468.68049MaRDI QIDQ3922168
Publication date: 1981
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322276.322281
Related Items
A unified approach to geometric problems using dual cone transformation:, An application of $m$-ary trees to the design of data structures for geometric searching problems, How hard is half-space range searching?, Query time versus redundancy trade-offs for range queries, On the time-space complexity of reachability queries for preprocessed graphs, Inherent complexity trade-offs for range query problems, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, On the equivalence of some rectangle problems, Can visibility graphs be represented compactly?, Dynamic orthogonal range queries in OLAP., A deterministic skip list for \(k\)-dimensional range search, A data structure for dynamic range queries, An algorithm for handling many relational calculus queries efficiently., Lower bounds for set intersection queries, Lower bounds for off-line range searching, Efficient data structures for adaptive remeshing with the FEM, Lower Bounds on the Complexity of Polytope Range Searching, A new approach to rectangle intersections part I, A new approach to rectangle intersections, A worst-case efficient algorithm for hidden-line elimination†