Recommendations
Cites work
- scientific article; zbMATH DE number 3887061 (Why is no real title available?)
- scientific article; zbMATH DE number 4152425 (Why is no real title available?)
- scientific article; zbMATH DE number 3533716 (Why is no real title available?)
- A Lower Bound on the Complexity of Orthogonal Range Queries
- A theorem on non-homogeneous lattices
- Applications of a new space-partitioning technique
- Applications of random sampling in computational geometry. II
- Convex bodies, economic cap coverings, random polytopes
- Geometric algorithms and combinatorial optimization
- Geometric retrieval problems
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Inherent complexity trade-offs for range query problems
- Lower Bounds on the Complexity of Polytope Range Searching
- Lower Bounds on the Complexity of Some Optimal Data Structures
- Lower bounds for orthogonal range searching: I. The reporting case
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- On the Complexity of Maintaining Partial Sums
- On the mean value of the volume of a random polytope in a convex set
- Polygon Retrieval
- Quasi-optimal range searching in spaces of finite VC-dimension
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
- The directions of the line segments and of the r ‐dimensional balls on the boundary of a convex body in Euclidean space
- \(\epsilon\)-nets and simplex range queries
Cited in
(29)- Lower bounds for intersection searching and fractional cascading in higher dimension
- Economical convex coverings and applications
- Approximate range searching: The absolute model
- Approximate range searching
- Range searching with efficient hierarchical cuttings
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- Approximate range searching in higher dimension
- Optimal halfspace range reporting in three dimensions
- Tight lower bounds for halfspace range searching
- Simplex Range Searching and Its Variants: A Review
- The effect of corners on the complexity of approximate range searching
- On semialgebraic range reporting
- On range searching in the group model and combinatorial discrepancy
- Tight lower bounds for halfspace range searching
- On the difficulty of range searching
- On the combinatorial complexity of approximating polytopes
- The power of nonmonotonicity in geometric searching
- Lower bounds for intersection searching and fractional cascading in higher dimension
- New lower bounds for Hopcroft's problem
- Efficient independent set approximation in unit disk graphs
- Reporting points in halfspaces
- 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
- Halfspace range search: An algorithmic application of k-sets
- \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets
- Space-Time Tradeoffs for Emptiness Queries
- scientific article; zbMATH DE number 1554935 (Why is no real title available?)
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
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)
