Lower Bounds on the Complexity of Polytope Range Searching
From MaRDI portal
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
Cites work
- -nets and simplex range queries
- A Compactness Theorem For Affine Equivalence-Classes of Convex Regions
- A Lower Bound for Heilbronn'S Problem
- A Lower Bound on the Complexity of Orthogonal Range Queries
- Geometric retrieval problems
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- scientific article; zbMATH DE number 3887060 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3533716 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- Inherent complexity trade-offs for range query problems
- Lower Bounds on the Complexity of Some Optimal Data Structures
- On the Complexity of Maintaining Partial Sums
- Polygon Retrieval
- Quasi-optimal range searching in spaces of finite VC-dimension
Cited in
(55)- 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
- Generalizations of Heilbronn's triangle problem
- General methods for adding range restrictions to decomposable searching problems
- On \(k\)-sets in arrangements of curves and surfaces
- Reporting points in halfspaces
- Efficient partition trees
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- On range searching with semialgebraic sets
- Can visibility graphs be represented compactly?
- Orthogonal queries in segments
- The power of nonmonotonicity in geometric searching
- Approximate range searching
- New lower bounds for Hopcroft's problem
- Quasi-optimal range searching in spaces of finite VC-dimension
- Lower bounds for intersection searching and fractional cascading in higher dimension
- Dynamic half-space range reporting and its applications
- Lower bounds for set intersection queries
- Simplex range reporting on a pointer machine
- Approximate range searching: The absolute model
- Multilevel polynomial partitions and simplified range searching
- Lower bounds for off-line range searching
- Distributions of points in the unit square and large \(k\)-gons
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- Improved points approximation algorithms based on simplicial thickness data structures
- Spanning trees with low crossing number
- Generalizations of Heilbronn's Triangle Problem
- On k-d Range Search with Patricia Tries
- Tight lower bounds for halfspace range searching
- Optimal partition trees
- scientific article; zbMATH DE number 512812 (Why is no real title available?)
- Space-Time Tradeoffs for Emptiness Queries
- Simplex Range Searching and Its Variants: A Review
- scientific article; zbMATH DE number 1405797 (Why is no real title available?)
- Lower bounds in on-line geometric searching metric searching
- On range searching with semialgebraic sets
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- Query complexity of sampling and small geometric partitions
- Tight lower bounds for halfspace range searching
- Lower bounds in on-line geometric searching
- Heilbronn triangle‐type problems in the unit square [0,1]2
- On semialgebraic range reporting
- On Heilbronn triangle-type problems in higher dimensions
- 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
- On ray shooting in convex polytopes
- The power of parallel projection
- Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
- Lower bounds for semialgebraic range searching and stabbing problems
- Lower bounds for semialgebraic range searching and stabbing problems
- Segment proximity graphs and nearest neighbor queries amid disjoint segments
- A deterministic partition tree and applications
- Partitioning arrangements of lines. II: Applications
- Enclosing weighted points with an almost-unit ball
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)
