A Lower Bound on the Complexity of Orthogonal Range Queries
From MaRDI portal
Publication:3922168
DOI10.1145/322276.322281zbMath0468.68049OpenAlexW1972755533MaRDI 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
An algorithm for handling many relational calculus queries efficiently., Lower bounds for off-line range searching, Can visibility graphs be represented compactly?, Lower bounds for set intersection queries, Efficient data structures for adaptive remeshing with the FEM, Polynomial Data Structure Lower Bounds in the Group Model, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, Improved bounds on absolute positiveness of multivariate polynomials, A unified approach to geometric problems using dual cone transformation:, Dynamic orthogonal range queries in OLAP., Biased range trees, Simplex Range Searching and Its Variants: A Review, On the time-space complexity of reachability queries for preprocessed graphs, On the equivalence of some rectangle problems, Multidimensional segment trees can do range updates in poly-logarithmic time, A worst-case efficient algorithm for hidden-line elimination†, Semi-group range sum revisited: query-space lower bound tightened, How hard is half-space range searching?, A deterministic skip list for \(k\)-dimensional range search, Lower Bounds on the Complexity of Polytope Range Searching, Partial sums on the ultra-wide word RAM, A New Lower Bound for Semigroup Orthogonal Range Searching, Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model, An application of $m$-ary trees to the design of data structures for geometric searching problems, A new approach to rectangle intersections part I, A new approach to rectangle intersections, A data structure for dynamic range queries, Inherent complexity trade-offs for range query problems, Query time versus redundancy trade-offs for range queries
