Tight lower bounds for halfspace range searching

DOI10.1145/1810959.1810964zbMATH Open1284.68579OpenAlexW2061544335MaRDI QIDQ5405859FDOQ5405859

Authors Sunil Arya, David M. Mount, Jian Xia

Publication date 3 April 2014

Published in Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.308.5994

zbMATH Keywords

range searchinglower boundsidempotence

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Tight lower bounds for halfspace range searching
• How hard is half-space range searching?
• A Spectral Approach to Lower Bounds with Applications to Geometric Searching
• Lower Bounds on the Complexity of Polytope Range Searching
• On the importance of idempotence

Cited in

(10)

• Tight bounds for blind search on the integers
• How hard is half-space range searching?
• Tight lower bounds for halfspace range searching
• On range searching in the group model and combinatorial discrepancy
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Quasi-optimal range searching in spaces of finite VC-dimension
• scientific article; zbMATH DE number 1263218 (Why is no real title available?)
• Optimal partition trees
• On the importance of idempotence
• Semi-group range sum revisited: query-space lower bound tightened

This page was built for publication: Tight lower bounds for halfspace range searching

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