# zbMATH — the first resource for mathematics

An (almost) optimal solution for orthogonal point enclosure query in $$\mathbb{R}^3$$. (English) Zbl 1434.68135
Summary: 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 $$\mathbb{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 $$\mathbb{R}^1$$ and $$\mathbb{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 $$\mathbb{R}^3$$ has been elusive. In this work, we obtain the first data structure that almost optimally solves the OPEQ in $$\mathbb{R}^3$$ in the pointer machine model: an $$O(n \log^\ast n)$$-space data structure with $$O(\log^2n \cdot \log \log n + k)$$ query time. Here, $$\log^\ast 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 $$\mathbb{R}^3$$. Finally, we also obtain the best known bounds for the OPEQ in higher dimensions $$(d \geq 4)$$.
##### MSC:
 68P05 Data structures 68P10 Searching and sorting 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 68W40 Analysis of algorithms
Full Text: