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

DOI10.1145/79147.79149zbMATH Open0699.68058OpenAlexW2038521122MaRDI QIDQ3477952FDOQ3477952

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

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

zbMATH Keywords

data structuresorthogonal range searchingLower boundsdominance search

Mathematics Subject Classification ID

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

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
• The power of nonmonotonicity in geometric searching
• Space efficient dynamic orthogonal range reporting
• Tight lower bounds for halfspace range searching
• On range searching in the group model and combinatorial discrepancy
• How hard is half-space range searching?
• 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
• A New Lower Bound for Semigroup Orthogonal Range Searching
• Lower bounds for off-line 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
• Simplex Range Searching and Its Variants: A Review
• Lower Bounds on the Complexity of Polytope Range Searching
• Query time versus redundancy trade-offs for range queries
• On the Complexity of Maintaining Partial Sums
• Title not available (Why is that?)

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)