Изменения
→Запрос точек в прямоугольнике
На рисунке среди вершин 3, 4, 5, 6 только 5 является критической.
Вместо поиска всех пронзающих вершин, для решения задачи достаточно найти все критические вершины.
Пусть r - радиус описанной вокруг R окружности.
{{Лемма
|about=
Об упаковке
|statement=
Существует такая константа c, зависящая от размерности пространства d и метрики на нем, что количество критических вершин на нулевом уровне дерева с длинной стороны как минимум s равно <tex>c \cdot (\frac{s}{r})^{1-d}</tex>.
|proof=
Рассмотрим квадродерево T(C), состоящее только из критических вершин.
Назовем вершину T(C) ветвящейся, если у нее есть как минимум два ребенка. Не ветвящаяся вершина - лист или такая, что ее единственный ребенок содержит меньшую часть <tex>\varepsilon</tex>-области. Две вершины квадродерева покрывают разные области R(не обязательно непересекающиеся), только если они пересекают границу R в разных местах. Поэтому они покрывают разные области E.
Таким образом, для каждой неветвящейся вершины существует уникальная область E, покрываемая только этой вершиной и никакой другой. Объем этой области составляет <tex>\frac{s^{d-1} \cdot \varepsilon \cdot r}{c}</tex>, так как каждая критическая вершина - гиперкуб со стороной <tex>2^i \cdot s</tex>.
Итоговое количество неветвящихся вершин в T(C) равно <tex>c \cdot (\frac{s}{r})^{1-d}</tex>, так как объем E равен <tex>O(\varepsilon \cdot r^d)</tex>. Так как в нашем дереве все вершины являются критическими, то лемма доказана.
}}
== Источник ==
