A Lower Bound on the Complexity of Orthogonal Range Queries

Cited in

(30)

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.
Semi-group range sum revisited: query-space lower bound tightened
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
Improved bounds on absolute positiveness of multivariate polynomials
Multidimensional segment trees can do range updates in poly-logarithmic time
Lower bounds for off-line range searching
Biased range trees
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^†
A unified approach to geometric problems using dual cone transformation:
Simplex Range Searching and Its Variants: A Review
An application of m-ary trees to the design of data structures for geometric searching problems
Polynomial data structure lower bounds in the group model
A New Lower Bound for Semigroup Orthogonal Range Searching
Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model
Partial sums on the ultra-wide word RAM
How hard is half-space range searching?
Quantum data structure for range minimum query
Query time versus redundancy trade-offs for range queries
On the time-space complexity of reachability queries for preprocessed graphs

This page was built for publication: A Lower Bound on the Complexity of Orthogonal Range Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3922168)