A New Lower Bound for Semigroup Orthogonal Range Searching

DOI10.4230/LIPICS.SOCG.2019.3OpenAlexW2921314108MaRDI QIDQ5088928FDOQ5088928

Authors: Peyman Afshani 

Publication date: 18 July 2022

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

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

zbMATH Keywords

data structuresrange searchinglower bounds

Mathematics Subject Classification ID

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

Cites Work

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

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)