On the difficulty of range searching.

DOI10.1016/S0925-7721(97)00005-9MaRDI QIDQ2482904zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 25 April 2008

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0925-7721(97)00005-9

zbMATH Keywords

Data structuresLower boundRange searching

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the difficulty of range searching
• On the computational complexity of the range computation problem
• scientific article; zbMATH DE number 1182924
• Approximate range searching in higher dimension
• Approximate range searching
• On a problem of optimal searching.
• On the hardness of range assignment problems
• On the Hardness of Range Assignment Problems
• scientific article; zbMATH DE number 1241835
• Topological complexity of the range searching

Cites work

• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Decomposable searching problems
• Efficient worst-case data structures for range searching
• Filtering Search: A New Approach to Query-Answering
• scientific article; zbMATH DE number 1263186 (Why is no real title available?)
• scientific article; zbMATH DE number 1306898 (Why is no real title available?)
• Lower bounds for orthogonal range searching: I. The reporting case
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Lower bounds for union-split-find related problems on random access machines
• Priority Search Trees
• Quad trees: A data structure for retrieval by composite keys
• Surpassing the information theoretic bound with fusion trees

Cited in

(13)

• Range searching in low-density environments
• Time complexity of multidimensional range queries in multiple storage units.
• Two-dimensional range diameter queries
• Quantum algorithmic methods for computational geometry
• On a model of indexability and its bounds for range queries
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Efficient data structures for range searching on a grid
• Optimal partition trees
• scientific article; zbMATH DE number 1953879 (Why is no real title available?)
• Towards tight lower bounds for range reporting on the RAM
• On the difficulty of range searching
• Concurrent range reporting in two-dimensional space
• Optimal partition trees

This page was built for publication: On the difficulty of range searching.

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