An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3
From MaRDI portal
Publication:5108270
DOI10.1287/moor.2019.0994zbMath1434.68135OpenAlexW2979588271MaRDI QIDQ5108270
Publication date: 30 April 2020
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.2019.0994
analysis of algorithmsdata structuresrange searchingquery timerectangle stabbingorthogonal point locationsize of data structure
Analysis of algorithms (68W40) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- A class of algorithms which require nonlinear time to maintain disjoint sets
- Making data structures persistent
- Finding pairwise intersections inside a query range
- Simplex range reporting on a pointer machine
- Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model
- IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS
- An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries
- Lower bounds for orthogonal range searching: I. The reporting case
- On Dominance Reporting in 3D
- A new approach to rectangle intersections part I
- Optimal Point Location in a Monotone Subdivision
- Filtering Search: A New Approach to Query-Answering
- Applications of a Planar Separator Theorem
- Optimal Search in Planar Subdivisions
- On Finding the Maxima of a Set of Vectors
- Optimal External Memory Interval Management
- Approximate range counting revisited
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- An Improved Algorithm for Static 3D Dominance Reporting in the Pointer Machine
- Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in ℝ3
- Concurrent Range Reporting in Two-Dimensional Space
- Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges
- Orthogonal range reporting
- Data Structures for One-Dimensional Packet Classification Using Most-Specific-Rule Matching
- Algorithms - ESA 2003
