Lower Bounds on the Complexity of Some Optimal Data Structures

DOI10.1137/0210001MaRDI QIDQ3902460zbMATH OpenOpenAlexFDO

Authors Michael L. Fredman

Publication date 1981

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0210001

zbMATH Keywords

range queries

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Cited in

(18)

• The effect of corners on the complexity of approximate range searching
• Inherent complexity trade-offs for range query problems
• Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems
• Lower bounds on zero-one matrices.
• New lower bounds for Hopcroft's problem
• Quasi-optimal range searching in spaces of finite VC-dimension
• Lower bounds for dynamic algebraic problems
• An algorithm for handling many relational calculus queries efficiently.
• Lower bounds for off-line range searching
• Lower Bounds on the Complexity of Polytope Range Searching
• Tight lower bounds for halfspace range searching
• Simplex Range Searching and Its Variants: A Review
• An application of m-ary trees to the design of data structures for geometric searching problems
• A New Lower Bound for Semigroup Orthogonal Range Searching
• scientific article; zbMATH DE number 2230258 (Why is no real title available?)
• How hard is half-space range searching?
• Query time versus redundancy trade-offs for range queries
• On the time-space complexity of reachability queries for preprocessed graphs

This page was built for publication: Lower Bounds on the Complexity of Some Optimal Data Structures

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