A Spectral Approach to Lower Bounds with Applications to Geometric Searching

DOI10.1137/S0097539794275665MaRDI QIDQ4388885zbMATH OpenOpenAlexFDO

Authors Bernard Chazelle

Publication date 10 May 1998

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

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

zbMATH Keywords

circuit complexityeigenvalueslower boundsrange searching

Mathematics Subject Classification ID

Real and complex geometry (51M99) Data structures (68P05) Discrete mathematics in relation to computer science (68R99) Parallel algorithms in computer science (68W10)

Recommendations

• Tight lower bounds for halfspace range searching
• Tight lower bounds for halfspace range searching
• How hard is half-space range searching?
• Lower bounds for off-line range searching
• On range searching in the group model and combinatorial discrepancy

Cited in

(7)

• The power of nonmonotonicity in geometric searching
• Lower bounds for off-line range searching
• The power of nonmonotonicity in geometric searching
• Simplex Range Searching and Its Variants: A Review
• Lower bounds in on-line geometric searching metric searching
• Tight lower bounds for halfspace range searching
• Lower bounds in on-line geometric searching

This page was built for publication: A Spectral Approach to Lower Bounds with Applications to Geometric Searching

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