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

DOI10.1016/0890-5401(89)90064-3MaRDI QIDQ1124391zbMATH OpenOpenAlexFDO

Authors 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

addition-subtraction operationsdata structureslower boundsorthogonal range queries

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3961018
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Lower bounds for orthogonal range searching: I. The reporting case
• Lower bounds for off-line range searching
• The cell probe complexity of dynamic range counting

Cites work

• A data structure for dynamic range queries
• A Lower Bound on the Complexity of Orthogonal Range Queries
• Adding range restriction capability to dynamic data structures
• Data Structures for Retrieval on Square Grids
• Decomposable searching problems I. Static-to-dynamic transformation
• Efficient worst-case data structures for range searching
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 3911764 (Why is no real title available?)
• scientific article; zbMATH DE number 3919834 (Why is no real title available?)
• scientific article; zbMATH DE number 4037201 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Lower Bounds on the Complexity of Some Optimal Data Structures
• Multidimensional binary search trees used for associative searching
• Multidimensional divide-and-conquer
• New Data Structures for Orthogonal Range Queries
• On the Complexity of Maintaining Partial Sums
• On the equivalence of some rectangle problems
• Polygon Retrieval
• Quintary trees
• The spanning bound as a measure of range query complexity
• Two general methods for dynamizing decomposable searching problems
• Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees

Cited in

(3)

• An algorithm for handling many relational calculus queries efficiently.
• scientific article; zbMATH DE number 3961018 (Why is no real title available?)
• Non-orthogonal homothetic range partial-sum query on integer grids (extended abstract)

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

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