Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
From MaRDI portal
Publication:2875643
DOI10.1142/S0218195913600054zbMATH Open1300.68051MaRDI QIDQ2875643FDOQ2875643
Publication date: 11 August 2014
Published in: International Journal of Computational Geometry \& Applications (Search for Journal in Brave)
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
- Efficient partition trees
- New applications of random sampling in computational geometry
- Filtering Search: A New Approach to Query-Answering
- A deterministic view of random sampling and its use in geometry
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Lower bounds for orthogonal range searching: I. The reporting case
- Efficient searching with linear constraints
- Cutting hyperplanes for divide-and-conquer
- Simplex range reporting on a pointer machine
- Polygon Retrieval
- Tight lower bounds for halfspace range searching
- Space-Time Tradeoffs for Emptiness Queries
- Range searching with efficient hierarchical cuttings
- Lower bounds for intersection searching and fractional cascading in higher dimension
- On a model of indexability and its bounds for range queries
- Optimal external memory planar point enclosure
Cited In (4)
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)
