Lower Bounds on the Complexity of Polytope Range Searching
From MaRDI portal
Publication:3471697
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
- 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?)
- 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
- 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
- -nets and simplex range queries
Cited in
(50)- Distributions of points in the unit square and large \(k\)-gons
- Space-Time Tradeoffs for Emptiness Queries
- scientific article; zbMATH DE number 1405797 (Why is no real title available?)
- The power of parallel projection
- Multilevel polynomial partitions and simplified range searching
- New lower bounds for Hopcroft's problem
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- On ray shooting in convex polytopes
- On range searching with semialgebraic sets
- On semialgebraic range reporting
- Tight lower bounds for halfspace range searching
- Dynamic half-space range reporting and its applications
- Query complexity of sampling and small geometric partitions
- Tight lower bounds for halfspace range searching
- 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
- On range searching with semialgebraic sets
- Generalizations of Heilbronn's Triangle Problem
- Point sets in the unit square and large areas of convex hulls of subsets of points
- Improved points approximation algorithms based on simplicial thickness data structures
- Lower bounds in on-line geometric searching
- 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
- On Heilbronn triangle-type problems in higher dimensions
- 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
- Approximate range searching
- Spanning trees with low crossing number
- Orthogonal queries in segments
- Optimal partition trees
- Lower bounds in on-line geometric searching metric searching
- Heilbronn triangle‐type problems in the unit square [0,1]2
- Simplex Range Searching and Its Variants: A Review
- scientific article; zbMATH DE number 512812 (Why is no real title available?)
- Partitioning arrangements of lines. II: Applications
- Lower bounds for set intersection queries
- 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)
