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

• 成果类型: Article
• 署名作者: Rahul, Saladi
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.0994
• 发表日期: 2020
• 页码: 369-383
• 关键词: lower bounds; search; algorithms; location

摘要

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 R-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 R-1 and R-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 R-3 has been elusive. In this work, we obtain the first data structure that almost optimally solves the OPEQ in R-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 Omega(log(2) n + k) time to answer an OPEQ in R-3. Finally, we also obtain the best known bounds for the OPEQ in higher dimensions (d >= 4).