Cache-oblivious range reporting with optimal queries requires superlinear space

DOI10.1007/s00454-011-9347-7zbMath1215.68103OpenAlexW4239171964MaRDI QIDQ540448

Peyman Afshani, Norbert Zeh, Chris H. Hamilton

Publication date: 3 June 2011

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

Full work available at URL: https://doi.org/10.1007/s00454-011-9347-7

zbMATH Keywords

lower boundrange reportingcache-obliviousness

Mathematics Subject Classification ID

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

Related Items (1)

Cache-oblivious hashing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient searching with linear constraints
• Efficient splitting and merging algorithms for order decomposable problems.
• Organization and maintenance of large ordered indexes
• Algorithms for three-dimensional dominance searching in linear space.
• On Dominance Reporting in 3D
• On the limits of cache-obliviousness
• Priority Search Trees
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• Cache-oblivious data structures for orthogonal range searching
• Cache-oblivious planar orthogonal range searching and counting
• Cache-oblivious R-trees
• A general approach for cache-oblivious range reporting and approximate range counting

This page was built for publication: Cache-oblivious range reporting with optimal queries requires superlinear space