Simplex range reporting on a pointer machine
From MaRDI portal
Publication:1917035
DOI10.1016/0925-7721(95)00002-XzbMath0851.68113MaRDI QIDQ1917035
Bernard Chazelle, Burton Rosenberg
Publication date: 14 July 1996
Published in: Computational Geometry (Search for Journal in Brave)
Related Items (12)
Lower bounds for off-line range searching ⋮ Lower bounds for intersection searching and fractional cascading in higher dimension ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3 ⋮ On semialgebraic range reporting ⋮ Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions ⋮ Optimal partition trees ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Unnamed Item ⋮ New lower bounds for Hopcroft's problem ⋮ Top tree compression of tries ⋮ IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS
Cites Work
- Unnamed Item
- Unnamed Item
- A class of algorithms which require nonlinear time to maintain disjoint sets
- \(\epsilon\)-nets and simplex range queries
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Polygonal intersection searching
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Quasi-optimal range searching in spaces of finite VC-dimension
- Lower Bounds on the Complexity of Polytope Range Searching
- Lower bounds for orthogonal range searching: I. The reporting case
- Filtering Search: A New Approach to Query-Answering
- Point retrieval for polygons
- Polygon Retrieval
- On Heilbronn's Triangle Problem
- A Lower Bound for Heilbronn'S Problem
This page was built for publication: Simplex range reporting on a pointer machine
