Lower bounds for orthogonal range searching: I. The reporting case
From MaRDI portal
Publication:3474276
DOI10.1145/77600.77614zbMath0696.68051OpenAlexW2093120238MaRDI QIDQ3474276
Publication date: 1990
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.983
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05)
Related Items
An algorithm for handling many relational calculus queries efficiently., I/O-efficient 2-d orthogonal range skyline and attrition priority queues, Optimal external memory planar point enclosure, Lower bounds for intersection searching and fractional cascading in higher dimension, On position restricted substring searching in succinct space, On the difficulty of range searching, Orthogonal queries in segments, Enabling high-dimensional range queries using \(k\)NN indexing techniques: approaches and empirical results, The range 1 query (R1Q) problem, Range searching in multidimensional databases using navigation metadata, Approximate covering detection among content-based subscriptions using space filling curves, Simplex range reporting on a pointer machine, Finding pairwise intersections of rectangles in a query rectangle, Entropy-bounded representation of point grids, Ranked Document Retrieval in External Memory, An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3, Dynamic orthogonal range queries in OLAP., On semialgebraic range reporting, Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions, Reasoning about visibility, Coloring lines and Delaunay graphs with respect to boxes, Unnamed Item, How hard is half-space range searching?, On the difficulty of range searching., OPTIMAL RANGE MAX DATACUBE FOR FIXED DIMENSIONS, A new framework for addressing temporal range queries and some preliminary results, Lower bounds on the complexity of simplex range reporting on a pointer machine, The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching, On the minimum total length of interval systems expressing all intervals, and range-restricted queries, On data structures and asymmetric communication complexity, Top tree compression of tries, Unnamed Item, Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines, Permuting and Batched Geometric Lower Bounds in the I/O Model, Orthogonal Range Searching for Text Indexing, Indexes for Document Retrieval with Relevance, Multivariate analysis of orthogonal range searching and graph distances, Geometric BWT: compressed text indexing via sparse suffixes and range searching, Fast Diameter Computation within Split Graphs, IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS
