Изменения

[[Файл:Skip_quadtree.png | 500px | thumb | По картинке должно быть понятно]]Skip quadtree {{---}} как skip list, только вместо list'а quadtree. Поэтому желательно знатьструктура данных, что такое напоминающая [[Список с пропусками | skip -list]], которая позволяет эффективно локализоваться и необходимо знать, что такое [[Квадродеревья#Сжатое квадродерево | сжатое квадродерево]]. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажетсяпроизводить операции над множеством точек.

В данной статье будет рассматриваться только рандомизированая версия этой структуры. The randomized skip quadtree {{---}} последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества точек <tex>S</tex>. <tex>S_0 = S</tex>, в <tex>S_1S_i</tex> каждый элемент из <tex>S_0S_{i-1}</tex> входит с вероятностью <tex>p \in (0, 1)</tex> и так далее, то есть <tex>S_i \subset S_{i-1}</tex>. The randomized skip quadtree состоит из последовательности <tex>\{Q_i\}</tex>, где <tex>Q_i</tex> {{---}} [[Квадродеревья#Сжатое квадродерево | сжатое квадродерево ]] над множеством <tex>S_i</tex>. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из <tex>S</tex>.ЗаметимНа рисунке представлено дерево, состоящее из трех слоев: <tex>Q_0</tex>, <tex>Q_1</tex>, <tex>Q_2</tex>. Одинаковые вершины, находящиеся на разных уровнях, соединены линиями. Стрелками обозначены переходы в процессе локализации при поиске точки <tex>y</tex>. Любая вершина однозначно определяется своими координатами на каждом уровне. Поэтому по вершине с уровня <tex>i</tex> мы можем получить ее на уровне <tex>i - 1</tex>, что если какой-то квадрат она [[Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)#interesting | интересныйинтересная]] на уровне <tex>i</tex>, так как в противном случае она могла быть сжата.  Заметим, что если какой-то квадрат интересный в <tex>Q_i</tex>, то он интересный и в <tex>Q_{i-1}</tex>, так как <tex>S_i \subset S_{i-1}</tex> по определению структуры.

Будем для каждого интересного квадрата Для реализации операций нам нужно уметь получать по вершине с уровня <tex>i</tex> соответствующую ей вершину с уровня <tex>i - 1</tex>. Сделать это можно двумя способами:* Хранить в вершине ссылку на каждом уровне хранить указатели на тот же квадрат вершину уровнем ниже и уровнем выше (если есть).* Так как каждая вершина однозначно задается своими координатами, можем сопоставить ей маску. Используем ассоциативный массив, чтобы по маске получать ссылку на вершину. Такие массивы будем хранить для каждого уровня skip quadtree.

===Локализация===Локализация выполняется аналогично сжатому квадродеревулокализации в сжатом квадродереве. Под локализацией подразумевается, что мы хотим найти минимальный интересный квадрат, геометрически содержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня уровнем ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далееНо на каждом уровне, кроме нулевого, локализумся не до листа, а до глубочайшего интересного. Продолжаем, пока не дойдём до днанулевого уровня.

Для добавления ===Вставка===При вставке сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в , запоминая ссылки, дальше добавляем вершину на нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно может увеличиться максимум на <tex>1</tex>, то есть, если появился новый уровень, то процесс точно заканчивается. Хотя не, давайте без последнего условия, вроде с ним только лучше, но без него проще доказывать.

===Удаление совсем просто: ===При удалении локализуемся, и удаляем вершину со всех уровней, на которых она есть, не забывая обновлять ссылки или ассоциативный массив. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.

Задача: нам дается прямоугольник, нужно выдать все точки, лежащие в нем.  Реализация запроса на сжатом квадродереве занимает <tex>O(n)</tex> времени. Используем skip quadtree для ускорения поиска. Для этого ослабим условие задачи, тогда skip quadtree позволит очень быстро (асимптотически) отвечать на такие запросы.  Ослабление: расширим данный прямоугольник на <tex>\varepsilon</tex>.Тогда в ответ могут попасть точки не из данного прямоугольника, но лежащие внутри <tex>\varepsilon</tex>-области. В большинстве практических задач данное ослабление не ухудшит конечный результат, а только ускорит процесс. 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>.

[[Файл: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(|B|D_T)</tex>, где B - множество пронзающих вершин, D_T - глубина нашего дерева T.

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

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

На рисунке среди вершин 3, 4, 5, 6 только 5 является ''критической''.

Вместо поиска всех ''пронзающих '' вершин, для решения задачи достаточно найти все ''критические '' вершины.Пусть r - радиус описанной вокруг R окружности.

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

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

Таким образом''Пронзающих'' вершин c длиной стороны чуть больше <tex>\varepsilon</tex>, области которых не пересекаются, для каждой неветвящейся вершины существует уникальная область Eможет быть <tex>O(\varepsilon^{-1})</tex> {{---}} длина стороны прямоугольника, покрываемая только этой вершиной и никакой другойделенная на <tex>\varepsilon</tex>. Объем этой области составляет Тогда всего их может быть <tex>\Omegavarepsilon^{-1} + \genfrac{}{}{}{0}{1}{2} \cdot \varepsilon^{-1} + \genfrac{}{}{}{0}{1}{4} \cdot \varepsilon^{-1} + \dots \ = \ O(\varepsilon^{-1})</tex>, так как каждая критическая вершина - гиперкубпронзающие вершины могут быть вложенными, и длина стороны родителя в два раза больше, чем у ребенка, то количество родителей вершин с такой стороной в два раза меньше.

Итоговое количество неветвящихся ''Критических'' вершин в T(C) равно не больше, чем ''пронзающих'', так что их тоже <tex>O(\varepsilon^{-1-d})</tex>, так как объем E равен <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>.

* http://arxiv.org/pdf/cs.cg/0507049.pdf* http://www.ics.uci.edu/~goodrich/pubs/skip.pdf