Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems

DOI10.1016/0890-5401(89)90064-3zbMath0678.68114OpenAlexW2073380464MaRDI QIDQ1124391

Dan E. Willard

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

zbMATH Keywords

data structureslower boundsorthogonal range queriesaddition-subtraction operations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Related Items (1)

An algorithm for handling many relational calculus queries efficiently.

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

This page was built for publication: Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems