Improved range searching lower bounds

DOI10.1145/2261250.2261275MaRDI QIDQ2874579zbMATH OpenOpenAlexFDO

Authors Kasper Green Larsen, Huy Le Nguyen

Publication date 7 August 2014

Published in Proceedings of the twenty-eighth 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.297.1217

zbMATH Keywords

group modellower boundspointer machinerange searching

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds for orthogonal range searching: I. The reporting case
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• On range searching in the group model and combinatorial discrepancy
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• On the difficulty of range searching

Cited in

(13)

• Improved range minimum queries
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Lower bounds for orthogonal range searching: I. The reporting case
• Tight lower bounds for halfspace range searching
• scientific article; zbMATH DE number 1263218 (Why is no real title available?)
• Simplex Range Searching and Its Variants: A Review
• scientific article; zbMATH DE number 6146456 (Why is no real title available?)
• On the difficulty of range searching
• Polynomial data structure lower bounds in the group model
• A New Lower Bound for Semigroup Orthogonal Range Searching
• On range searching in the group model and combinatorial discrepancy
• scientific article; zbMATH DE number 7760157 (Why is no real title available?)

This page was built for publication: Improved range searching lower bounds

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