Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
From MaRDI portal
Publication:2875643
Recommendations
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- Simplex range reporting on a pointer machine
- Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines
- Improved range searching lower bounds
- Lower bounds for orthogonal range searching: I. The reporting case
- Towards tight lower bounds for range reporting on the RAM
- Lower Bounds on the Complexity of Polytope Range Searching
- Improved space bounds for cache-oblivious range reporting
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
Cites work
- A deterministic view of random sampling and its use in geometry
- Cutting hyperplanes for divide-and-conquer
- Efficient partition trees
- Efficient searching with linear constraints
- Filtering Search: A New Approach to Query-Answering
- Lower bounds for intersection searching and fractional cascading in higher dimension
- Lower bounds for orthogonal range searching: I. The reporting case
- New applications of random sampling in computational geometry
- On a model of indexability and its bounds for range queries
- Optimal external memory planar point enclosure
- Polygon Retrieval
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Range searching with efficient hierarchical cuttings
- Simplex range reporting on a pointer machine
- Space-Time Tradeoffs for Emptiness Queries
- Tight lower bounds for halfspace range searching
Cited in
(11)- Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines
- Lower bounds for intersection reporting among flat objects
- An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3
- Simplex range reporting on a pointer machine
- Simplex Range Searching and Its Variants: A Review
- Improved range searching lower bounds
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- Lower bounds for sorted geometric queries in the I/O model
- Towards tight lower bounds for range reporting on the RAM
- Permuting and batched geometric lower bounds in the I/O model
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
This page was built for publication: Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875643)
