Lower Bounds on the Complexity of Polytope Range Searching
From MaRDI portal
Publication:3471697
DOI10.2307/1990891zbMath0695.68032OpenAlexW4252217479MaRDI QIDQ3471697
Publication date: 1989
Full work available at URL: https://doi.org/10.2307/1990891
Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Polytopes and polyhedra (52Bxx)
Related Items (35)
On range searching with semialgebraic sets ⋮ Lower bounds for off-line range searching ⋮ Can visibility graphs be represented compactly? ⋮ Lower bounds for intersection searching and fractional cascading in higher dimension ⋮ Dynamic half-space range reporting and its applications ⋮ Orthogonal queries in segments ⋮ Lower bounds for set intersection queries ⋮ Simplex range reporting on a pointer machine ⋮ Heilbronn triangle‐type problems in the unit square [0,12] ⋮ Generalizations of Heilbronn's Triangle Problem ⋮ On semialgebraic range reporting ⋮ Distributions of points in the unit square and large \(k\)-gons ⋮ Tight lower bounds for halfspace range searching ⋮ Optimal partition trees ⋮ Partitioning arrangements of lines. II: Applications ⋮ On \(k\)-sets in arrangements of curves and surfaces ⋮ Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Reporting points in halfspaces ⋮ How hard is half-space range searching? ⋮ Range searching with efficient hierarchical cuttings ⋮ On ray shooting in convex polytopes ⋮ The power of parallel projection ⋮ Efficient partition trees ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ Approximate range searching: The absolute model ⋮ Enclosing weighted points with an almost-unit ball ⋮ Spanning trees with low crossing number ⋮ Lower bounds on the complexity of simplex range reporting on a pointer machine ⋮ The effect of corners on the complexity of approximate range searching ⋮ Point sets in the unit square and large areas of convex hulls of subsets of points ⋮ New lower bounds for Hopcroft's problem ⋮ On range searching with semialgebraic sets ⋮ Generalizations of Heilbronn's triangle problem ⋮ Approximate range searching
Cites Work
- 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
- Quasi-optimal range searching in spaces of finite VC-dimension
- On the Complexity of Maintaining Partial Sums
- Geometric retrieval problems
- Lower Bounds on the Complexity of Some Optimal Data Structures
- A Lower Bound on the Complexity of Orthogonal Range Queries
- Polygon Retrieval
- A Lower Bound for Heilbronn'S Problem
- A Compactness Theorem For Affine Equivalence-Classes of Convex Regions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Lower Bounds on the Complexity of Polytope Range Searching
