How hard is half-space range searching?
From MaRDI portal
Publication:685178
DOI10.1007/BF02573971zbMath0778.68087WikidataQ29394177 ScholiaQ29394177MaRDI QIDQ685178
Hervé Brönnimann, János Pach, Bernard Chazelle
Publication date: 30 September 1993
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131267
68Q25: Analysis of algorithms and problem complexity
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Related Items
The effect of corners on the complexity of approximate range searching, Approximate range searching, New lower bounds for Hopcroft's problem, Approximate range searching in higher dimension
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inherent complexity trade-offs for range query problems
- \(\epsilon\)-nets and simplex range queries
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Applications of a new space-partitioning technique
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Geometric algorithms and combinatorial optimization
- Applications of random sampling in computational geometry. II
- Quasi-optimal range searching in spaces of finite VC-dimension
- On the mean value of the volume of a random polytope in a convex set
- A theorem on non-homogeneous lattices
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
- Lower Bounds on the Complexity of Polytope Range Searching
- Lower bounds for orthogonal range searching: I. The reporting case
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- On the Complexity of Maintaining Partial Sums
- Geometric retrieval problems
- Convex bodies, economic cap coverings, random polytopes
- Lower Bounds on the Complexity of Some Optimal Data Structures
- A Lower Bound on the Complexity of Orthogonal Range Queries
- Polygon Retrieval
- Lower bounds on the complexity of simplex range reporting on a pointer machine
- The directions of the line segments and of the r ‐dimensional balls on the boundary of a convex body in Euclidean space
