A New Lower Bound for Semigroup Orthogonal Range Searching

DOI10.4230/LIPICS.SOCG.2019.3MaRDI QIDQ5088928zbMATH OpenOpenAlexFDO

Authors Peyman Afshani

Publication date 18 July 2022

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

zbMATH Keywords

data structuresrange searchinglower bounds

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Semi-group range sum revisited: query-space lower bound tightened
• Tight lower bounds for halfspace range searching
• Tight lower bounds for halfspace range searching
• Improved range searching lower bounds

Cites work

• scientific article; zbMATH DE number 1182924 (Why is no real title available?)
• A Lower Bound on the Complexity of Orthogonal Range Queries
• 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
• Lower Bounds on the Complexity of Some Optimal Data Structures
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Multidimensional divide-and-conquer
• On the complexity of range searching among curves
• On the importance of idempotence

Cited in

(3)

• On semialgebraic range reporting
• Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model
• Semialgebraic Range Reporting and Emptiness Searching with Applications

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

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