Lower Bounds on the Complexity of Polytope Range Searching
From MaRDI portal
Publication:3471697
DOI10.2307/1990891zbMATH Open0695.68032OpenAlexW4252217479MaRDI QIDQ3471697FDOQ3471697
Authors: Bernard Chazelle 
Publication date: 1989
Full work available at URL: https://doi.org/10.2307/1990891
Recommendations
- How hard is half-space range searching?
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- Simplex range reporting on a pointer machine
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- Quasi-optimal range searching in spaces of finite VC-dimension
Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Polytopes and polyhedra (52Bxx)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Compactness Theorem For Affine Equivalence-Classes of Convex Regions
- \(\epsilon\)-nets and simplex range queries
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Lower Bounds on the Complexity of Some Optimal Data Structures
- Polygon Retrieval
- Geometric retrieval problems
- Inherent complexity trade-offs for range query problems
- A Lower Bound on the Complexity of Orthogonal Range Queries
- A Lower Bound for Heilbronn'S Problem
Cited In (50)
- On Heilbronn triangle-type problems in higher dimensions
- Distributions of points in the unit square and large \(k\)-gons
- Title not available (Why is that?)
- Multilevel polynomial partitions and simplified range searching
- The power of parallel projection
- New lower bounds for Hopcroft's problem
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- On range searching with semialgebraic sets
- On semialgebraic range reporting
- On ray shooting in convex polytopes
- Query complexity of sampling and small geometric partitions
- Tight lower bounds for halfspace range searching
- Tight lower bounds for halfspace range searching
- Dynamic half-space range reporting and its applications
- On counting pairs of intersecting segments and off-line triangle range searching
- How hard is half-space range searching?
- Range searching with efficient hierarchical cuttings
- Efficient partition trees
- 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
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- Reporting points in halfspaces
- Generalizations of Heilbronn's Triangle Problem
- On range searching with semialgebraic sets
- Improved points approximation algorithms based on simplicial thickness data structures
- Lower bounds in on-line geometric searching
- Point sets in the unit square and large areas of convex hulls of subsets of points
- Quasi-optimal range searching in spaces of finite VC-dimension
- General methods for adding range restrictions to decomposable searching problems
- Simplex range reporting on a pointer machine
- Can visibility graphs be represented compactly?
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- On k-d Range Search with Patricia Tries
- Approximate range searching: The absolute model
- Lower bounds for off-line range searching
- Generalizations of Heilbronn's triangle problem
- On \(k\)-sets in arrangements of curves and surfaces
- Heilbronn triangle‐type problems in the unit square [0,1]2
- Spanning trees with low crossing number
- Lower bounds in on-line geometric searching metric searching
- Approximate range searching
- Simplex Range Searching and Its Variants: A Review
- Orthogonal queries in segments
- Optimal partition trees
- Title not available (Why is that?)
- Partitioning arrangements of lines. II: Applications
- Lower bounds for set intersection queries
- Enclosing weighted points with an almost-unit ball
- Space-Time Tradeoffs for Emptiness Queries
This page was built for publication: Lower Bounds on the Complexity of Polytope Range Searching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3471697)
