Изменения
→Удаление
== Описание ==
[[Файл: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> по определению структуры.
== Операции над skip quadtree ==
===Локализация===Локализация выполняется аналогично сжатому квадродеревулокализации в сжатом квадродереве. Под локализацией подразумевается, что мы хотим найти минимальный интересный квадрат, геометрически содержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня уровнем ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далееНо на каждом уровне, кроме нулевого, локализумся не до листа, а до глубочайшего интересного. Продолжаем, пока не дойдём до днанулевого уровня.
===Удаление совсем просто: ===При удалении локализуемся, и удаляем вершину со всех уровней, на которых она есть, не забывая обновлять ссылки или ассоциативный массив. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.
== Время работы и память ==
==Запрос точек в прямоугольнике==
Задача: нам дается прямоугольник, нужно выдать все точки, лежащие в нем.
Реализация запроса на сжатом квадродереве занимает <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> {{---}} число точек в ответе. Алгоритм можно модифицировать для ответа на запрос точек в любой выпуклой фигуре.
[[Файл: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 является ''критической''.
Вместо поиска всех ''пронзающих '' вершин, для решения задачи достаточно найти все ''критические '' вершины.Пусть <tex>r</tex> {{---}} радиус описанной вокруг <tex>R</tex> окружности.
{{Лемма
Об упаковке
|statement=
Количество критических ''критически''х вершин на нулевом уровне дерева равно <tex>O(\varepsilon^{-1-d})</tex>.
|proof=
}}
===Алгоритм===
Начинаем отвечать на запрос с корня <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 level = k - 1 // максимальный уровень, на котором вершина q некритическая // k - количество уровней в skip quadtree '''while''' (level > 0) node <tex>n_{level}</tex> = n from <tex>Q_{level}</tex> // вершина, соответствующая n в дереве <tex>Q_{level}</tex> '''if''' (<tex>n_{level}</tex> != null '''and''' <tex>n_{level}</tex> is not critical) q = <tex>n_{level}</tex> '''break''' level--
'''while''' (true)
'''if''' (q is not critical)
'''else'''
'''break'''
que.push(q)
'''else'''
que.add_all(n.children)
== Источник ==
* http://arxiv.org/pdf/cs.cg/0507049.pdf* http://www.ics.uci.edu/~goodrich/pubs/skip.pdf
[[Категория: Вычислительная геометрия]]
[[Категория: Структуры данных]]