Изменения
→Запрос точек в прямоугольнике
==Запрос точек в прямоугольнике==
Skip quadtree позволяет отвечать на запрос всех точек, лежащих в прямоугольнике, окруженном <tex>\varepsilon</tex>-областью, за <tex>O(\log n + \varepsilon^{-1}\cdot \log n + k)</tex>, где k - число точек в ответе. Алгоритм можно модифицировать для ответа на запрос точек в любой выпуклой фигуре.
Обозначим наш прямоугольник R. Тогда <tex>\varepsilon</tex>-область {{---}} область E, охватывающая R, граница которой удалена от его сторон на <tex>\varepsilon</tex>.
Об упаковке
|statement=
Существует такая константа c, зависящая от размерности пространства d и метрики на нем, что количество критических вершин на нулевом уровне дерева с длинной стороны как минимум s равно <tex>c \cdot O(\frac{s}{r})varepsilon^{1-d})</tex>.
|proof=
Рассмотрим квадродерево T(C), состоящее только из критических вершин.
Назовем вершину T(C) ветвящейся, если у нее есть как минимум два ребенка. Не ветвящаяся вершина - лист или такая, что ее единственный ребенок содержит меньшую часть <tex>\varepsilon</tex>-области. Две вершины квадродерева покрывают разные области R(не обязательно непересекающиеся), только если они пересекают границу R в разных местах. Поэтому они покрывают разные области E.
Таким образом, для каждой неветвящейся вершины существует уникальная область E, покрываемая только этой вершиной и никакой другой. Объем этой области составляет <tex>\frac{s^{d-Omega(1} \cdot \varepsilon \cdot r}{c})</tex>, так как каждая критическая вершина - гиперкуб со стороной <tex>2^i \cdot s</tex>.
Итоговое количество неветвящихся вершин в T(C) равно <tex>c \cdot O(\frac{s}{r})varepsilon^{1-d})</tex>, так как объем E равен <tex>O(\varepsilon \cdot r^d)</tex>. Так как в нашем дереве все вершины являются критическими, то лемма доказана.
}}
===Алгоритм===
Начинаем отвечать на запрос с корня Q_0 и определяем тип вершин.
* Если вершина внутренняя, добавляем ее в ответ вместе с поддеревом.
* Если внешняя, то игнорируем.
* Если критическая, то рассмотрим всех ее детей.
* Если не критическая, то найдем минимальную критическую, содержащую ту же часть E, что и рассматриваемая вершина.
Первые три варианта рассматриваются тривиально. Покажем, как для данной некритической вершины p найти минимальную критическую вершину q, содержащую ту же часть E, что и p. Для это найдем такое Q_i, что p будет критической вершиной в Q_i при максимальном i. И будем действовать аналогично процессу локализации.
Таким образом, поиск q займет <tex>O(\log n)</tex> времени. А так как критических вершин всего <tex>O(\varepsilon^{-1})</tex>, то итоговая ассимптотика составит <tex>O(\varepsilon^{-1} \cdot \log n + k)</tex>.
===Псевдокод===
== Источник ==
