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
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
