Изменения
→Запрос точек в прямоугольнике
[[Файл:Skip_quadtree_rect.png|right|400px]]
Данный прямоугольник <tex>R</tex> разбивает вершины на следующие классы:
* <tex>\mathrm{in}</tex> {{---}} ''внутренние'', то есть лежащие внутри <tex>\varepsilon</tex>-области (1 и 6 на рисунке).* <tex>\mathrm{out}</tex> {{---}} ''внешние'', то есть лежащие вне прямоугольника <tex>R</tex> (2 на рисунке).* <tex>\mathrm{stabbing}</tex> {{---}} ''пронзающие'', пересекающие <tex>R</tex>, но не являющие являющиеся ''внутренними '' (3, 4 и 5 на рисунке).
Для вершин из классов <tex>\mathrm{in}</tex> и <tex>\mathrm{out}</tex> ответ на запрос находится тривиально {{---}} все поддерево вершины и никакие точки из поддерева соответственно; сложность представляют вершины из класса <tex>\mathrm{stabbing}</tex>. Зная их все, мы можем ответить на запрос.
Мощность множества ''пронзающих '' вершин может составлять <tex>O(n)</tex>, так как ''пронзающие '' вершины могут быть вложены друг в друга, тогда как нам достаточно рассмотреть только наименьшую из вложенных вершин.
Назовем ''пронзающую '' вершину ''критической'', если для каждого из ее детей выполняется одно из двух условий:* ребенок не является ''пронзающей '' вершиной.* ребенок является ''пронзающим'', но содержит меньшую часть <tex>E</tex>, чем рассматриваемая вершина.
На рисунке среди вершин 3, 4, 5, 6 только 5 является ''критической''.
Вместо поиска всех ''пронзающих '' вершин, для решения задачи достаточно найти все ''критические '' вершины.
{{Лемма
Об упаковке
|statement=
Количество критических ''критически''х вершин на нулевом уровне дерева равно <tex>O(\varepsilon^{1-d})</tex>, где <tex>d</tex> - размерность пространства.
|proof=
Рассмотрим квадродерево <tex>T</tex>, состоящее только из ''критических '' вершин.
Назовем вершину дерева <tex>T</tex> ветвящейся, если у нее есть как минимум два ребенка. Не ветвящаяся вершина {{---}} лист или такая, что ее единственный ребенок содержит меньшую часть <tex>\varepsilon</tex>-области. Две вершины квадродерева покрывают разные области <tex>R</tex> (не обязательно непересекающиеся), только если они пересекают границу <tex>R</tex> в разных местах. Поэтому они покрывают разные области <tex>E</tex>.
Таким образом, для каждой неветвящейся вершины существует уникальная область <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>. Так как в нашем дереве все вершины являются ''критическими'', то лемма доказана.
}}
===Алгоритм===
Начинаем отвечать на запрос с корня <tex>Q_0</tex> и определяем тип вершин.
* Если вершина ''внутренняя'', добавляем ее в ответ вместе с поддеревом.* Если ''внешняя'', то игнорируем.* Если ''критическая'', то рассмотрим всех ее детей.* Если не ''критическая'', то найдем минимальную ''критическую'', содержащую ту же часть <tex>E</tex>, что и рассматриваемая вершина.
Первые три варианта рассматриваются тривиально. Покажем, как для данной некритической вершины <tex>p</tex> найти минимальную критическую вершину <tex>q</tex>, содержащую ту же часть <tex>E</tex>, что и <tex>p</tex>. Для это найдем такое <tex>Q_i</tex>, что <tex>p</tex> будет ''критической '' вершиной в <tex>Q_i</tex> при максимальном <tex>i</tex>. И будем действовать аналогично процессу локализации.
Таким образом, поиск <tex>q</tex> займет <tex>O(\log n)</tex> времени. А так как ''критических '' вершин всего <tex>O(\varepsilon^{-1})</tex>, то итоговая ассимптотика составит <tex>O(\varepsilon^{-1} \cdot \log n + k)</tex>.
===Псевдокод===
points.push_back(n.point)
'''else if''' (K <tex>\subset</tex> E)
n.add_subtree(points) // добавляем все точки поддерева ''внутренней '' вершины
'''else if''' (n is not critical)
'''node''' q // некритическая вершина на максимальном уровне i, соответствующая n
