Предлагается модификация алгоритма Бентли-Маурера, решающего
двумерную задачу интервального поиска. Эта модификация
позволяет снизить исходное логарифмическое среднее время
поиска до константного при сохранении логарифмического
времени поиска в худшем случае. При этом этот алгоритм
зависит от параметра, при вариации которого объем памяти,
необходимый алгоритму, изменяется от
![$O(k^3)$](images/ofunksl/img1.gif)
до
![$O(k\log k)$](images/ofunksl/img2.gif)
,
при этом среднее время поиска (без учета времени на
перечисление ответа) изменяется от
![$O(1)$](images/ofunksl/img3.gif)
до
![$O(\log k)$](images/ofunksl/img4.gif)
.
В частности, для любого
![$\varepsilon>0$](images/ofunksl/img5.gif)
при объеме памяти
![$O(k^{1+\varepsilon})$](images/ofunksl/img6.gif)
достигается среднее время поиска
![$O(1)$](images/ofunksl/img3.gif)
. На основе этих результатов
получены верхние оценки
функциональной сложности двумерной задачи интервального
поиска.