Lower bounds for orthogonal range searching: part II. The arithmetic model

DOI10.1145/79147.79149MaRDI QIDQ3477952zbMATH OpenOpenAlexFDO

Authors Bernard Chazelle

Publication date 1990

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/79147.79149

zbMATH Keywords

data structuresorthogonal range searchingLower boundsdominance search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Recommendations

• Lower bounds for orthogonal range searching: I. The reporting case
• Lower bounds for off-line range searching
• How hard is half-space range searching?
• On the difficulty of range searching.
• Tight lower bounds for halfspace range searching

Cited in

(30)

• The cell probe complexity of dynamic range counting
• OPTIMAL RANGE MAX DATACUBE FOR FIXED DIMENSIONS
• Space-Time Trade-Offs for Orthogonal Range Queries
• An efficient \(k\) nearest neighbors searching algorithm for a query line.
• On semialgebraic range reporting
• Space efficient dynamic orthogonal range reporting
• The power of nonmonotonicity in geometric searching
• Tight lower bounds for halfspace range searching
• How hard is half-space range searching?
• On range searching in the group model and combinatorial discrepancy
• On the difficulty of range searching
• Polynomial data structure lower bounds in the group model
• Dynamic orthogonal range queries in OLAP.
• Semi-group range sum revisited: query-space lower bound tightened
• On the minimum total length of interval systems expressing all intervals, and range-restricted queries
• Lower bounds for orthogonal range searching: I. The reporting case
• On the difficulty of range searching.
• A new framework for addressing temporal range queries and some preliminary results
• Can visibility graphs be represented compactly?
• The range 1 query (R1Q) problem
• Approximate range searching: The absolute model
• Lower bounds for off-line range searching
• A New Lower Bound for Semigroup Orthogonal Range Searching
• Approximate covering detection among content-based subscriptions using space filling curves
• Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems
• Query time versus redundancy trade-offs for range queries
• Simplex Range Searching and Its Variants: A Review
• Lower Bounds on the Complexity of Polytope Range Searching
• On the Complexity of Maintaining Partial Sums
• scientific article; zbMATH DE number 3961018 (Why is no real title available?)

This page was built for publication: Lower bounds for orthogonal range searching: part II. The arithmetic model

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