A New Lower Bound for Semigroup Orthogonal Range Searching

DOI10.4230/LIPIcs.SoCG.2019.3OpenAlexW2921314108MaRDI QIDQ5088928

Peyman Afshani

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1903.07967

zbMATH Keywords

data structureslower boundsrange searching

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (1)

On semialgebraic range reporting

Cites Work

• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• A class of algorithms which require nonlinear time to maintain disjoint sets
• Decomposable searching problems
• Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model
• On the importance of idempotence
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Lower Bounds on the Complexity of Some Optimal Data Structures
• A Lower Bound on the Complexity of Orthogonal Range Queries

This page was built for publication: A New Lower Bound for Semigroup Orthogonal Range Searching