How hard is half-space range searching?
From MaRDI portal
Publication:685178
DOI10.1007/BF02573971zbMath0778.68087OpenAlexW1995232397WikidataQ29394177 ScholiaQ29394177MaRDI QIDQ685178
János Pach, Hervé Brönnimann, 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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (13)
Polynomial Data Structure Lower Bounds in the Group Model ⋮ Efficient independent set approximation in unit disk graphs ⋮ On the combinatorial complexity of approximating polytopes ⋮ On semialgebraic range reporting ⋮ Tight lower bounds for halfspace range searching ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Approximate range searching in higher dimension ⋮ \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets ⋮ Approximate range searching: The absolute model ⋮ The effect of corners on the complexity of approximate range searching ⋮ New lower bounds for Hopcroft's problem ⋮ Economical Delone Sets for Approximating Convex Bodies ⋮ Approximate range searching
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
This page was built for publication: How hard is half-space range searching?
