How hard is half-space range searching?
From MaRDI portal
Publication:685178
DOI10.1007/BF02573971zbMATH Open0778.68087DBLPjournals/dcg/BronnimannCP93OpenAlexW1995232397WikidataQ29394177 ScholiaQ29394177MaRDI QIDQ685178FDOQ685178
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Geometric algorithms and combinatorial optimization
- Title not available (Why is that?)
- \(\epsilon\)-nets and simplex range queries
- Applications of random sampling in computational geometry. II
- Title not available (Why is that?)
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Convex bodies, economic cap coverings, random polytopes
- Lower bounds for orthogonal range searching: I. The reporting case
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- Title not available (Why is that?)
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Applications of a new space-partitioning technique
- Quasi-optimal range searching in spaces of finite VC-dimension
- Lower Bounds on the Complexity of Polytope Range Searching
- On the Complexity of Maintaining Partial Sums
- Lower Bounds on the Complexity of Some Optimal Data Structures
- Polygon Retrieval
- On the mean value of the volume of a random polytope in a convex set
- A theorem on non-homogeneous lattices
- The directions of the line segments and of the r ‐dimensional balls on the boundary of a convex body in Euclidean space
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
- Geometric retrieval problems
- Inherent complexity trade-offs for range query problems
- A Lower Bound on the Complexity of Orthogonal Range Queries
- Lower bounds on the complexity of simplex range reporting on a pointer machine
Cited In (25)
- New lower bounds for Hopcroft's problem
- On semialgebraic range reporting
- Tight lower bounds for halfspace range searching
- Economical convex coverings and applications
- Range searching with efficient hierarchical cuttings
- On the difficulty of range searching
- The power of nonmonotonicity in geometric searching
- Lower bounds for intersection searching and fractional cascading in higher dimension
- The effect of corners on the complexity of approximate range searching
- Halfspace range search: An algorithmic application of k-sets
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Reporting points in halfspaces
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- Approximate range searching: The absolute model
- Efficient independent set approximation in unit disk graphs
- On the combinatorial complexity of approximating polytopes
- Title not available (Why is that?)
- Approximate range searching in higher dimension
- Approximate range searching
- Simplex Range Searching and Its Variants: A Review
- Lower Bounds on the Complexity of Polytope Range Searching
- Polynomial Data Structure Lower Bounds in the Group Model
- Economical Delone Sets for Approximating Convex Bodies
- Space-Time Tradeoffs for Emptiness Queries
- \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets
This page was built for publication: How hard is half-space range searching?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685178)
