Lower bounds for off-line range searching

DOI10.1007/BF02770864zbMath0864.68021OpenAlexW2086303161MaRDI QIDQ2365324

Bernard Chazelle

Publication date: 22 January 1997

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02770864

zbMATH Keywords

range-searching problem

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (2)

IMPROVED ALGORITHMS FOR THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE 3-TREES ⋮ Polygonal path simplification with angle constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Range searching with efficient hierarchical cuttings
• New lower bounds for Hopcroft's problem
• Simplex range reporting on a pointer machine
• Lower Bounds on the Complexity of Polytope Range Searching
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• On the Complexity of Maintaining Partial Sums
• Lower Bounds on the Complexity of Some Optimal Data Structures
• A Lower Bound on the Complexity of Orthogonal Range Queries
• A Spectral Approach to Lower Bounds with Applications to Geometric Searching
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• On irregularities of distribution

This page was built for publication: Lower bounds for off-line range searching