Изменения

Skip quadtree позволяет отвечать на запрос всех точек, лежащих в прямоугольнике, окруженном <tex>\varepsilon</tex>-областью, за <tex>O(\varepsilon^{-1} \cdot \log n + k)</tex>, где <tex>k </tex> {{- --}} число точек в ответе. Алгоритм можно модифицировать для ответа на запрос точек в любой выпуклой фигуре.

Обозначим наш прямоугольник <tex>R</tex>. Тогда <tex>\varepsilon</tex>-область {{---}} область <tex>E</tex>, охватывающая <tex>R</tex>, граница которой удалена от его сторон на <tex>\varepsilon</tex>.

Данный прямоугольник <tex>R </tex> разбивает вершины на следующие классы:* <tex>\mathrm{in }</tex> {{-- -}} внутренние, то есть лежащие внутри <tex>\varepsilon</tex>-области (1 на рисунке).* <tex>\mathrm{out }</tex> {{- --}} внешние, то есть лежащие вне прямоугольника <tex>R </tex> (2 на рисунке).* <tex>\mathrm{stabbing }</tex> {{-- -}} пронзающие, пересекающие <tex>R</tex>, но не являющие внутренними (3 на рисунке).

Для вершин из классов <tex>\mathrm{in }</tex> и <tex>\mathrm{out }</tex> ответ на запрос находится тривиально, сложность представляют вершины из класса <tex>\mathrm{stabbing}</tex>. Зная их все, мы можем ответить на запрос.

Мощность множества B пронзающих вершин может составлять <tex>O(n)</tex>, так как пронзающие вершины могут быть вложены друг в друга, тогда как нам достаточно рассмотреть только наименьшую из вложенных вершин.

* ребенок является пронзающим, но содержит меньшую часть <tex>E</tex>, чем рассматриваемая вершина.

Пусть <tex>r </tex> {{- --}} радиус описанной вокруг <tex>R </tex> окружности.

Существует такая константа c, зависящая от размерности пространства d и метрики на нем, что количество Количество критических вершин на нулевом уровне дерева с длинной стороны как минимум s равно <tex>O(\varepsilon^{1-d})</tex>.

Рассмотрим квадродерево <tex>T(C)</tex>, состоящее только из критических вершин. Назовем вершину <tex>T(C) </tex> ветвящейся, если у нее есть как минимум два ребенка. Не ветвящаяся вершина {{- --}} лист или такая, что ее единственный ребенок содержит меньшую часть <tex>\varepsilon</tex>-области. Две вершины квадродерева покрывают разные области <tex>R</tex> (не обязательно непересекающиеся), только если они пересекают границу <tex>R </tex> в разных местах. Поэтому они покрывают разные области <tex>E</tex>.

Таким образом, для каждой неветвящейся вершины существует уникальная область <tex>E</tex>, покрываемая только этой вершиной и никакой другой. Объем этой области составляет <tex>\Omega(1)</tex>, так как каждая критическая вершина {{--- }} гиперкуб.

Итоговое количество неветвящихся вершин в <tex>T(C) </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>.