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

Saladi Rahul ()
Additional contact information
Saladi Rahul: Department of Computer Science, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801

Mathematics of Operations Research, 2020, vol. 45, issue 1, 369–383

Abstract: The orthogonal point enclosure query ( OPEQ ) problem is a fundamental problem in the context of data management for modeling user preferences. Formally, preprocess a set S of n axis-aligned boxes (possibly overlapping) in ℝ d into a data structure so that the boxes in S containing a given query point q can be reported efficiently. In the pointer machine model, optimal solutions for the OPEQ in ℝ 1 and ℝ 2 were discovered in the 1980s: linear-space data structures that can answer the query in O (log n + k ) query time, where k is the number of boxes reported. However, for the past three decades, an optimal solution in ℝ 3 has been elusive. In this work, we obtain the first data structure that almost optimally solves the OPEQ in ℝ 3 in the pointer machine model: an O ( n log* n )-space data structure with O (log 2 n · log log n + k ) query time. Here, log * n is the iterated logarithm of n . This almost matches the lower-bound, which states that any data structure that occupies O ( n ) space requires Ω (log 2 n + k ) time to answer an OPEQ in ℝ 3 . Finally, we also obtain the best known bounds for the OPEQ in higher dimensions ( d ≥ 4).

Keywords: ange searching; orthogonal point location; rectangle stabbing; query time; size of the data structure (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2019.0994 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:1:p:369-383

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().