Tight lower bounds for halfspace range searching

DOI10.1007/S00454-012-9412-XzbMath1248.68210OpenAlexW4248139057MaRDI QIDQ420572

Sunil Arya, Jian Xia, David M. Mount

Publication date: 22 May 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9412-x

zbMATH Keywords

lower boundsrange searchingidempotence

Mathematics Subject Classification ID

Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Efficient independent set approximation in unit disk graphs ⋮ On the combinatorial complexity of approximating polytopes ⋮ On semialgebraic range reporting ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Semi-group range sum revisited: query-space lower bound tightened ⋮ IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS

Cites Work

• Unnamed Item
• How hard is half-space range searching?
• Range searching with efficient hierarchical cuttings
• The effect of corners on the complexity of approximate range searching
• \(\epsilon\)-nets and simplex range queries
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Geometric algorithms and combinatorial optimization.
• Quasi-optimal range searching in spaces of finite VC-dimension
• Realistic input models for geometric algorithms
• Approximate range searching: The absolute model
• On the importance of idempotence
• Lower Bounds on the Complexity of Polytope Range Searching
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• On the Complexity of Maintaining Partial Sums
• Lower Bounds on the Complexity of Some Optimal Data Structures
• Polygon Retrieval
• Space-Time Tradeoffs for Emptiness Queries
• Optimal partition trees

This page was built for publication: Tight lower bounds for halfspace range searching