Lower bounds for orthogonal range searching: I. The reporting case

Recommendations

Lower bounds for orthogonal range searching: part II. The arithmetic model
Orthogonal range reporting, query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
Improved range searching lower bounds
Simplex range reporting on a pointer machine
On the difficulty of range searching

Cited in

(59)

On the minimum total length of interval systems expressing all intervals, and range-restricted queries
Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines
Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems
On data structures and asymmetric communication complexity
Orthogonal queries in segments
Dynamic orthogonal range queries in OLAP.
The range 1 query (R1Q) problem
A new framework for addressing temporal range queries and some preliminary results
An algorithm for handling many relational calculus queries efficiently.
Lower bounds for intersection searching and fractional cascading in higher dimension
Simplex range reporting on a pointer machine
Top tree compression of tries
Finding pairwise intersections of rectangles in a query rectangle
The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching
Geometric BWT: compressed text indexing via sparse suffixes and range searching
Lower bounds for off-line range searching
On position restricted substring searching in succinct space
On the difficulty of range searching.
Range searching in multidimensional databases using navigation metadata
Orthogonal range searching for text indexing
Indexes for document retrieval with relevance
Improved range searching lower bounds
Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model
Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
Enabling high-dimensional range queries using kNN indexing techniques: approaches and empirical results
Lower bounds for orthogonal range searching: part II. The arithmetic model
Approximate covering detection among content-based subscriptions using space filling curves
scientific article; zbMATH DE number 3961018 (Why is no real title available?)
Space-Time Trade-Offs for Orthogonal Range Queries
Entropy-bounded representation of point grids
Reasoning about visibility
scientific article; zbMATH DE number 1305452 (Why is no real title available?)
Towards tight lower bounds for range reporting on the RAM
OPTIMAL RANGE MAX DATACUBE FOR FIXED DIMENSIONS
Multivariate analysis of orthogonal range searching and graph distances
Fast diameter computation within split graphs
On the difficulty of range searching
An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³
Permuting and batched geometric lower bounds in the I/O model
Finding pairwise intersections of rectangles in a query rectangle
Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
Orthogonal range reporting, query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
Ranked Document Retrieval in External Memory
On semialgebraic range reporting
Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions
Coloring lines and Delaunay graphs with respect to boxes
How hard is half-space range searching?
Range reporting for time series via rectangle stabbing
Zarankiewicz's problem via -t-nets
On the number of incidences when avoiding an induced biclique in geometric settings
Lower bounds for semialgebraic range searching and stabbing problems
Lower bounds for semialgebraic range searching and stabbing problems
Sparse bounded hop-spanners for geometric intersection graphs
On Zarankiewicz's problem for intersection hypergraphs of geometric objects
On geometric bipartite graphs with asymptotically smallest Zarankiewicz numbers
Multivariate analysis of orthogonal range searching and graph distances
I/O-efficient 2-d orthogonal range skyline and attrition priority queues
Optimal external memory planar point enclosure

This page was built for publication: Lower bounds for orthogonal range searching: I. The reporting case

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