On the functional complexity of a two-dimensional interval search problem

We suggest a modification of the Bentley–Maurer algorithm which solves a two-dimensional interval search problem. This modification allows us to decrease the initially logarithmic average search time to constant, retaining the logarithmic worst-case search time. This algorithm depends on a parameter whose change results in variation of the needed memory from $\mathcal O(k^3)$ to $\mathcal O(k\log k)$; the average search time (without the time needed to output the answer) varies from $\mathcal O(1)$ to $\mathcal O(\log k)$. In particular, for any $\varepsilon>0$ and available memory $\mathcal O(k^{1+\varepsilon})$ the average search time is $\mathcal O(1)$. On the basis of these results, we give upper bounds for the functional complexity of a two-dimensional interval search problem.
This research was supported by the Russian Foundation for Basic Research, grants 98–01–00130, 01–01–00748.