Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems
From MaRDI portal
Publication:1124391
DOI10.1016/0890-5401(89)90064-3zbMath0678.68114MaRDI QIDQ1124391
Publication date: 1989
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(89)90064-3
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
68P20: Information storage and retrieval of data
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Efficient worst-case data structures for range searching
- Two general methods for dynamizing decomposable searching problems
- On the equivalence of some rectangle problems
- Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees
- A data structure for dynamic range queries
- New Data Structures for Orthogonal Range Queries
- On the Complexity of Maintaining Partial Sums
- Data Structures for Retrieval on Square Grids
- Adding range restriction capability to dynamic data structures
- Quintary trees
- Lower Bounds on the Complexity of Some Optimal Data Structures
- The spanning bound as a measure of range query complexity
- Decomposable searching problems I. Static-to-dynamic transformation
- A Lower Bound on the Complexity of Orthogonal Range Queries
- Polygon Retrieval
- Multidimensional binary search trees used for associative searching
