Изменения
→Запрос точек в прямоугольнике
Вместо поиска всех пронзающих вершин, для решения задачи достаточно найти все критические вершины.
{{Лемма
Таким образом, для каждой неветвящейся вершины существует уникальная область <tex>E</tex>, покрываемая только этой вершиной и никакой другой. Объем этой области составляет <tex>\Omega(1)</tex>, так как каждая критическая вершина {{---}} гиперкуб.
Пусть <tex>r</tex> {{---}} радиус описанной вокруг <tex>R</tex> окружности.
Итоговое количество неветвящихся вершин в <tex>T</tex> равно <tex>O(\varepsilon^{1-d})</tex>, так как объем <tex>E</tex> равен <tex>O(\varepsilon \cdot r^d)</tex>. Так как в нашем дереве все вершины являются критическими, то лемма доказана.
}}
