On the difficulty of range searching

DOI10.1007/3-540-60220-8_86MaRDI QIDQ5057458zbMATH OpenOpenAlexFDO

Authors

Publication date 16 December 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60220-8_86

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the difficulty of range searching.
• Lower bounds for orthogonal range searching: I. The reporting case
• Improved range searching lower bounds
• Orthogonal range searching in linear and almost-linear space
• How hard is half-space 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
• scientific article; zbMATH DE number 1263186 (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

Cited in

(13)

• The effect of corners on the complexity of approximate range searching
• Maintaining range trees in secondary memory. Part I: Partitions
• On data structures and asymmetric communication complexity
• The range 1 query (R1Q) problem
• On the difficulty of range searching.
• Improved range searching lower bounds
• Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model
• Two-dimensional range diameter queries
• Lower bounds for orthogonal range searching: I. The reporting case
• On k-d Range Search with Patricia Tries
• scientific article; zbMATH DE number 4051018 (Why is no real title available?)
• Space-Time Trade-Offs for Orthogonal Range Queries
• Space-Time Tradeoffs for Emptiness Queries

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 Q5057458)