Деревья решений с квазилинейными проверками

Пусть $k$ гиперплоскостей разбивает $n$-мерное действительное пространство на области. По произвольной точке пространства требуется найти область, содержащую эту точку. Линейное дерево решений – алгоритм, каждая операция которого состоит в определении положения точки относительно некоторой гиперплоскости. В предположении, что коэффициенты уравнений, задающих гиперплоскости, принадлежат произвольному числовому кольцу с единицей, получена верхняя оценка
$$ (2(n+2)^3\log_2(k+2n+2))/(\log_2(n+2)) $$
минимальной глубины линейного дерева решений для рассматриваемой задачи. Приведены обобщения и следствия этого результата.
Библиогр. 9.