Tight lower bounds for halfspace range searching
From MaRDI portal
Publication:420572
DOI10.1007/s00454-012-9412-xzbMath1248.68210MaRDI 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
68P10: Searching and sorting
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Simplex Range Searching and Its Variants: A Review, On semialgebraic range reporting, On the combinatorial complexity of approximating polytopes, Semi-group range sum revisited: query-space lower bound tightened, Efficient independent set approximation in unit disk graphs, 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
