An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3

DOI10.1287/moor.2019.0994zbMath1434.68135OpenAlexW2979588271MaRDI QIDQ5108270

Saladi Rahul

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

zbMATH Keywords

analysis of algorithmsdata structuresrange searchingquery timerectangle stabbingorthogonal point locationsize of data structure

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions

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 ℝ³
• 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