О функциональной сложности двумерной задачи интервального поиска

Предлагается модификация алгоритма Бентли–Маурера, решающего двумерную задачу интервального поиска. Эта модификация позволяет снизить исходное логарифмическое среднее время поиска до константного при сохранении логарифмического времени поиска в худшем случае. Этот алгоритм зависит от параметра, при вариации которого объем памяти, необходимый алгоритму, изменяется от $\mathcal O(k^3)$ до $\mathcal O(k\log k)$, при этом среднее время поиска (без учета времени на перечисление ответа) изменяется от $\mathcal O(1)$ до $\mathcal O(\log k)$. В частности, для любого $\varepsilon>0$ при объеме памяти $\mathcal O(k^{1+\varepsilon})$ достигается среднее время поиска $\mathcal O(1)$. На основе этих результатов получены верхние оценки функциональной сложности двумерной задачи интервального поиска.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, гранты 98–01–00130, 01–01–00748.