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