Skip quadtree: определение, время работы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Запрос точек в прямоугольнике)
м (rollbackEdits.php mass rollback)
 
(не показаны 42 промежуточные версии 9 участников)
Строка 1: Строка 1:
 
== Описание ==
 
== Описание ==
[[Файл:Skip_quadtree.png | 500px | thumb | По картинке должно быть понятно]]
+
[[Файл:Skip_quadtree.png | 500px | thumb]]
Skip quadtree {{---}} как skip list, только вместо list'а quadtree. Поэтому желательно знать, что такое [[Список с пропусками | skip list]], и необходимо знать, что такое [[Квадродеревья#Сжатое квадродерево | сжатое квадродерево]]. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажется.
+
Skip quadtree {{---}} структура данных, напоминающая [[Список с пропусками | skip-list]], которая позволяет эффективно локализоваться и производить операции над множеством точек.
  
The randomized skip quadtree {{---}} последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества <tex>S</tex>. <tex>S_0 = S</tex>, в <tex>S_1</tex> каждый элемент из <tex>S_0</tex> входит с вероятностью <tex>p \in (0, 1)</tex> и так далее. The randomized skip quadtree состоит из последовательности <tex>\{Q_i\}</tex>, где <tex>Q_i</tex> {{---}} сжатое квадродерево над множеством <tex>S_i</tex>. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из <tex>S</tex>.
+
В данной статье будет рассматриваться только рандомизированая версия этой структуры.
Заметим, что если какой-то квадрат [[Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)#interesting | интересный]] в <tex>Q_i</tex>, то он интересный и в <tex>Q_{i-1}</tex>.
+
 
 +
The randomized skip quadtree {{---}} последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества точек <tex>S</tex>. <tex>S_0 = S</tex>, в <tex>S_i</tex> каждый элемент из <tex>S_{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 ==
 
== Операции над skip quadtree ==
Будем для каждого интересного квадрата на каждом уровне хранить указатели на тот же квадрат уровнем ниже и уровнем выше (если есть).  
+
Для реализации операций нам нужно уметь получать по вершине с уровня <tex>i</tex> соответствующую ей вершину с уровня <tex>i - 1</tex>. Сделать это можно двумя способами:
 +
* Хранить в вершине ссылку на вершину уровнем ниже.
 +
* Так как каждая вершина однозначно задается своими координатами, можем сопоставить ей маску. Используем ассоциативный массив, чтобы по маске получать ссылку на вершину. Такие массивы будем хранить для каждого уровня skip quadtree.
  
Локализация выполняется аналогично сжатому квадродереву. Под локализацией подразумевается, что мы хотим найти минимальный интересный квадрат, содержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далее, пока не дойдём до дна.
+
===Локализация===
 +
Локализация выполняется аналогично локализации в сжатом квадродереве. Под локализацией подразумевается, что мы хотим найти минимальный интересный квадрат, геометрически содержащий данную точку. Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровнем ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. Но на каждом уровне, кроме нулевого, локализумся не до листа, а до глубочайшего интересного. Продолжаем, пока не дойдём до нулевого уровня.
  
Для добавления сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно увеличиться максимум на 1, то есть, если появился новый уровень, то процесс точно заканчивается. Хотя не, давайте без последнего условия, вроде с ним только лучше, но без него проще доказывать.
+
===Вставка===
 +
При вставке сначала локализуемся сразу на всех уровнях, запоминая ссылки, дальше добавляем вершину на нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней может увеличиться максимум на <tex>1</tex>, то есть, если появился новый уровень, то процесс заканчивается.
  
Удаление совсем просто: локализуемся, удаляем со всех уровней, на которых есть. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.
+
===Удаление===
 +
При удалении локализуемся и удаляем вершину со всех уровней, на которых она есть, не забывая обновлять ссылки или ассоциативный массив. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.
  
 
== Время работы и память ==
 
== Время работы и память ==
Строка 97: Строка 109:
  
 
==Запрос точек в прямоугольнике==
 
==Запрос точек в прямоугольнике==
Skip quadtree позволяет отвечать на запрос всех точек, лежащих в прямоугольнике, окруженном <tex>\varepsilon</tex>-областью, за <tex>O(\varepsilon^{-1} \cdot \log n + k)</tex>, где k - число точек в ответе. Алгоритм можно модифицировать для ответа на запрос точек в любой выпуклой фигуре.
+
Задача: нам дается прямоугольник, нужно выдать все точки, лежащие в нем.
 +
 
 +
Реализация запроса на сжатом квадродереве занимает <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> {{---}} число точек в ответе. Алгоритм можно модифицировать для ответа на запрос точек в любой выпуклой фигуре.
  
Обозначим наш прямоугольник R. Тогда <tex>\varepsilon</tex>-область {{---}} область E, охватывающая R, граница которой удалена от его сторон на <tex>\varepsilon</tex>.
+
Обозначим наш прямоугольник <tex>R</tex>. Тогда <tex>\varepsilon</tex>-область {{---}} область <tex>E</tex>, охватывающая <tex>R</tex>, граница которой удалена от его сторон на <tex>\varepsilon</tex>.
  
 
[[Файл:Skip_quadtree_rect.png|right|400px]]  
 
[[Файл:Skip_quadtree_rect.png|right|400px]]  
Данный прямоугольник R разбивает вершины на следующие классы:
+
Данный прямоугольник <tex>R</tex> разбивает вершины на следующие классы:
* in - внутренние, то есть лежащие внутри <tex>\varepsilon</tex>-области (1 на рисунке).
+
* <tex>\mathrm{in}</tex> {{---}} ''внутренние'', то есть лежащие внутри <tex>\varepsilon</tex>-области (1 и 6 на рисунке).
* out - внешние, то есть лежащие вне прямоугольника R (2 на рисунке).
+
* <tex>\mathrm{out}</tex> {{---}} ''внешние'', то есть лежащие вне прямоугольника <tex>R</tex> (2 на рисунке).
* stabbing - пронзающие, пересекающие R, но не являющие внутренними (3 на рисунке).
+
* <tex>\mathrm{stabbing}</tex> {{---}} ''пронзающие'', пересекающие <tex>R</tex>, но не являющиеся ''внутренними'' (3, 4 и 5 на рисунке).
  
Для вершин из классов in и out ответ на запрос находится тривиально, сложность представляют вершины из класса stabbing. Зная их все, мы можем ответить на запрос.  
+
Для вершин из классов <tex>\mathrm{in}</tex> и <tex>\mathrm{out}</tex> ответ на запрос находится тривиально {{---}} все поддерево вершины и никакие точки из поддерева соответственно; сложность представляют вершины из класса <tex>\mathrm{stabbing}</tex>. Зная их все, мы можем ответить на запрос.  
  
Мощность множества B может составлять O(n), так как пронзающие вершины могут быть вложены друг в друга, тогда как нам достаточно рассмотреть только наименьшую из вложенных вершин.
+
Мощность множества ''пронзающих'' вершин может составлять <tex>O(n)</tex>, так как ''пронзающие'' вершины могут быть вложены друг в друга, тогда как нам достаточно рассмотреть только наименьшую из вложенных вершин.
  
Назовем пронзающую вершину критической, если для каждого из ее детей выполняется одно из двух условий:
+
Назовем ''пронзающую'' вершину ''критической'', если для каждого из ее детей выполняется одно из двух условий:
* ребенок не является пронзающей вершиной.
+
* ребенок не является ''пронзающей'' вершиной.
* ребенок является пронзающим, но содержит меньшую часть E, чем рассматриваемая вершина.  
+
* ребенок является ''пронзающим'', но содержит меньшую часть <tex>E</tex>, чем рассматриваемая вершина.  
  
На рисунке среди вершин 3, 4, 5, 6 только 5 является критической.
+
На рисунке среди вершин 3, 4, 5, 6 только 5 является ''критической''.
  
Вместо поиска всех пронзающих вершин, для решения задачи достаточно найти все критические вершины.
+
Вместо поиска всех ''пронзающих'' вершин, для решения задачи достаточно найти все ''критические'' вершины.
Пусть r - радиус описанной вокруг R окружности.
 
  
 
{{Лемма
 
{{Лемма
Строка 124: Строка 142:
 
Об упаковке
 
Об упаковке
 
|statement=
 
|statement=
Существует такая константа c, зависящая от размерности пространства d и метрики на нем, что количество критических вершин на нулевом уровне дерева с длинной стороны как минимум s равно <tex>O(\varepsilon^{1-d})</tex>.  
+
Количество ''критически''х вершин на нулевом уровне дерева равно <tex>O(\varepsilon^{-1})</tex>.  
 
|proof=
 
|proof=
Рассмотрим квадродерево T(C), состоящее только из критических вершин.
+
Для квадратов с длиной стороны <tex>\varepsilon</tex> верно, что они либо <tex>\mathrm{in}</tex>, либо <tex>\mathrm{out}</tex>, то есть <tex>\mathrm{stabbing}</tex> вершин с такой стороной не бывает, как и со стороной меньше <tex>\varepsilon</tex>.
Назовем вершину T(C) ветвящейся, если у нее есть как минимум два ребенка. Не ветвящаяся вершина - лист или такая, что ее единственный ребенок содержит меньшую часть <tex>\varepsilon</tex>-области. Две вершины квадродерева покрывают разные области R(не обязательно непересекающиеся), только если они пересекают границу R в разных местах. Поэтому они покрывают разные области E.  
+
 
 +
Все точки, содержащиеся в skip quadtree, находятся внутри какого-то прямоугольника, значит, длина его стороны {{---}} константа. Поэтому длина стороны области пересечения запрашиваемого прямоугольника со skip quadtree {{---}} это тоже константа. Тогда длина стороны запрашиваемого прямоугольника {{---}} <tex>O(1)</tex>.
  
Таким образом, для каждой неветвящейся вершины существует уникальная область E, покрываемая только этой вершиной и никакой другой. Объем этой области составляет <tex>\Omega(1)</tex>, так как каждая критическая вершина - гиперкуб.  
+
''Пронзающих'' вершин c длиной стороны чуть больше <tex>\varepsilon</tex>, области которых не пересекаются, может быть <tex>O(\varepsilon^{-1})</tex> {{---}} длина стороны прямоугольника, деленная на <tex>\varepsilon</tex>. Тогда всего их может быть <tex>\varepsilon^{-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>O(\varepsilon^{-1})</tex>.
 
}}
 
}}
  
 
===Алгоритм===
 
===Алгоритм===
Начинаем отвечать на запрос с корня Q_0 и определяем тип вершин.
+
Начинаем отвечать на запрос с корня <tex>Q_0</tex> и определяем тип вершин.
* Если вершина внутренняя, добавляем ее в ответ вместе с поддеревом.
+
* Если вершина ''внутренняя'', добавляем ее в ответ вместе с поддеревом.
* Если внешняя, то игнорируем.
+
* Если ''внешняя'', то игнорируем.
* Если критическая, то рассмотрим всех ее детей.
+
* Если ''критическая'', то рассмотрим всех ее детей.
* Если не критическая, то найдем минимальную критическую, содержащую ту же часть E, что и рассматриваемая вершина.
+
* Если не ''критическая'', то найдем минимальную ''критическую'', содержащую ту же часть <tex>E</tex>, что и рассматриваемая вершина.
  
Первые три варианта рассматриваются тривиально. Покажем, как для данной некритической вершины p найти минимальную критическую вершину q, содержащую ту же часть E, что и p. Для это найдем такое Q_i, что p будет критической вершиной в Q_i при максимальном i. И будем действовать аналогично процессу локализации.  
+
Первые три варианта рассматриваются тривиально. Покажем, как для данной некритической вершины <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>. И будем действовать аналогично процессу локализации.  
  
Таким образом, поиск q займет <tex>O(\log n)</tex> времени. А так как критических вершин всего <tex>O(\varepsilon^{-1})</tex>, то итоговая ассимптотика составит <tex>O(\varepsilon^{-1} \cdot \log n + k)</tex>.
+
Таким образом, поиск <tex>q</tex> займет <tex>O(\log n)</tex> времени. А так как ''критических'' вершин всего <tex>O(\varepsilon^{-1})</tex>, то итоговая ассимптотика составит <tex>O(\varepsilon^{-1} \cdot \log n + k)</tex>.
  
 
===Псевдокод===
 
===Псевдокод===
     void points_in_rectangle(rectangle R, rectangle E, vector<point>& points)
+
     '''void''' points_in_rectangle('''rectangle''' R, '''rectangle''' E, '''vector<point>&''' points)
         queue<node> que
+
         '''queue<node>''' que
         que.push(Q_0.root)
+
         que.push(<tex>Q_0</tex>.root)
         while (!que.empty())
+
         '''while''' (!que.empty())
             node n = que.pop()
+
             '''node''' n = que.pop()
             rectangle quad // прямоугольник, соответсвующий вершине n
+
             '''rectangle''' K // прямоугольник, соответсвующий вершине n
             if (R \cap quad == \varnothing)  
+
             '''if''' (R <tex>\cap</tex> K == <tex>\varnothing</tex>)  
                 continue
+
                 '''continue'''
             else if (n is leaf)
+
             '''else if''' (n is leaf)
                 if (n.point in R)
+
                 '''if''' (n.point in R)
 
                     points.push_back(n.point)
 
                     points.push_back(n.point)
             else if (quad in E)  
+
             '''else if''' (K <tex>\subset</tex> E)  
                 n.add_subtree(points) // добавляем все точки поддерева внутренней вершины
+
                 n.add_subtree(points) // добавляем все точки поддерева ''внутренней'' вершины
             else if (n is not critical)
+
             '''else if''' (n is not critical)
                 node q // некритическая вершина на максимальном уровне i, соответствующая n
+
                 '''node''' q // некритическая вершина на максимальном уровне, соответствующая n
                 while (true)
+
                 level = k - 1 // максимальный уровень, на котором вершина q некритическая
                     if (q is not critical)
+
                // k - количество уровней в skip quadtree
                         q = ребенок q, содержащий ту же область E, что и q
+
                '''while''' (level > 0)
                     else if (i != 0)
+
                    node <tex>n_{level}</tex> = n from <tex>Q_{level}</tex> // вершина, соответствующая n в дереве <tex>Q_{level}</tex>
                         q = такая же вершина на уровень ниже i--
+
                    '''if''' (<tex>n_{level}</tex> != null '''and''' <tex>n_{level}</tex> is not critical)
                     else  
+
                        q = <tex>n_{level}</tex>
                         break
+
                        '''break'''
             else
+
                    level--
 +
                '''while''' (true)
 +
                     '''if''' (q is not critical)
 +
                         '''node''' qc = ребенок q, содержащий ту же область E, что и q
 +
                        '''if''' (qc is not leaf '''or''' level == 0)
 +
                            q = qc
 +
                        '''else if''' (level > 0)
 +
                            level--
 +
                            q = q from <tex>Q_{level}</tex>
 +
                     '''else if''' (level != 0)
 +
                        level--
 +
                         q = q from <tex>Q_{level}</tex>
 +
                     '''else'''
 +
                         '''break'''
 +
                que.push(q)
 +
             '''else'''
 
                 que.add_all(n.children)
 
                 que.add_all(n.children)
  
 
== Источник ==
 
== Источник ==
http://arxiv.org/pdf/cs.cg/0507049.pdf
+
* http://arxiv.org/pdf/cs.cg/0507049.pdf
 +
* http://www.ics.uci.edu/~goodrich/pubs/skip.pdf
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:19, 4 сентября 2022

Описание

Skip quadtree.png

Skip quadtree — структура данных, напоминающая skip-list, которая позволяет эффективно локализоваться и производить операции над множеством точек.

В данной статье будет рассматриваться только рандомизированая версия этой структуры.

The randomized skip quadtree — последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества точек [math]S[/math]. [math]S_0 = S[/math], в [math]S_i[/math] каждый элемент из [math]S_{i-1}[/math] входит с вероятностью [math]p \in (0, 1)[/math], то есть [math]S_i \subset S_{i-1}[/math]. The randomized skip quadtree состоит из последовательности [math]\{Q_i\}[/math], где [math]Q_i[/math] сжатое квадродерево над множеством [math]S_i[/math]. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из [math]S[/math].

На рисунке представлено дерево, состоящее из трех слоев: [math]Q_0[/math], [math]Q_1[/math], [math]Q_2[/math]. Одинаковые вершины, находящиеся на разных уровнях, соединены линиями. Стрелками обозначены переходы в процессе локализации при поиске точки [math]y[/math].

Любая вершина однозначно определяется своими координатами на каждом уровне. Поэтому по вершине с уровня [math]i[/math] мы можем получить ее на уровне [math]i - 1[/math], если она интересная на уровне [math]i[/math], так как в противном случае она могла быть сжата.

Заметим, что если какой-то квадрат интересный в [math]Q_i[/math], то он интересный и в [math]Q_{i-1}[/math], так как [math]S_i \subset S_{i-1}[/math] по определению структуры.

Операции над skip quadtree

Для реализации операций нам нужно уметь получать по вершине с уровня [math]i[/math] соответствующую ей вершину с уровня [math]i - 1[/math]. Сделать это можно двумя способами:

  • Хранить в вершине ссылку на вершину уровнем ниже.
  • Так как каждая вершина однозначно задается своими координатами, можем сопоставить ей маску. Используем ассоциативный массив, чтобы по маске получать ссылку на вершину. Такие массивы будем хранить для каждого уровня skip quadtree.

Локализация

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

Вставка

При вставке сначала локализуемся сразу на всех уровнях, запоминая ссылки, дальше добавляем вершину на нулевой уровень, затем с вероятностью [math]p[/math] добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней может увеличиться максимум на [math]1[/math], то есть, если появился новый уровень, то процесс заканчивается.

Удаление

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

Время работы и память

Лемма (О количестве шагов на одном уровне):
На каждом уровне в среднем совершается [math]O(1)[/math] шагов поиска для любой точки [math]x[/math].
Доказательство:
[math]\triangleright[/math]

Пусть в [math]Q_i[/math] (то есть на [math]i[/math]-ом уровне) поиск точки [math]x[/math], начинающийся с корня, проходит по квадратам [math]p_0, p_1, \dots, p_m[/math]. Пусть случайная величина [math]j[/math] — количество шагов поиска в [math]Q_i[/math], тогда [math]p_{m - j}[/math] — последний квадрат из [math]p_0, p_1, \dots, p_m[/math], являющийся интересным в [math]Q_{i + 1}[/math].

Оценим вероятность того, что делается [math]j[/math] шагов. Забьём на случай [math]j = 0[/math], так как он не важен при расчёте мат. ожидания. На пути [math]p_{m - j + 1} \dots, p_m[/math] будет хотя бы [math]j + 1[/math] непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустые четвертинки, одна из них — следующий квадрат на пути, в котором тоже хотя бы 2 непустые четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустые четвертинки. Чтобы [math]p_{m - j}[/math] был последним из [math]p_0, p_1, \dots, p_m[/math] интересным квадратом в [math]Q_{i + 1}[/math] небходимо, чтобы среди этих как минимум [math]j + 1[/math] непустых четвертинок только одна (вероятность этого назовём [math]Pr_1[/math]) или ноль (вероятность этого назовём [math]Pr_0[/math]) были непустыми в [math]Q_{i + 1}[/math]. Иначе, если будет хотя бы пара непустых четвертинок, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже [math]p_{m - j}[/math]. Таким образом, искомая вероятность не превосходит [math]Pr_0 + Pr_1[/math].


[math]q = 1 - p[/math]

[math]Pr_0 \leq q^{(j + 1)}[/math], потому что это в сущности вероятность того, что ни одна точка из как минимум [math]j + 1[/math] непустых четвертинок не попала на уровень выше.

[math]Pr_1 \leq (j + 1) \cdot pq^j[/math], потому что это в сущности вероятность того, что ровно одна точка из как минимум [math]j + 1[/math] непустых четвертинок попала на уровень выше.


[math]E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (q^{(j + 1)} + (j + 1) \cdot pq^j) \leq \sum\limits_{j = 1}^{\infty} j \cdot (q^{(j + 1)} + (j + 1) \cdot pq^j)[/math]

Это почти геометрическая прогрессия, только на полином домножили, определяется всё экспоненциальным множителем, так что это [math]O(1)[/math]. Можно совсем строго оценить, но и так понятно, что ряд сходится, а сойтись он может только к константе.
[math]\triangleleft[/math]
Лемма (О количестве уровней):
Математическое ожидание количества уровней составляет [math]O(\log(n))[/math]
Доказательство:
[math]\triangleright[/math]

Для оценки мат. ожидания посчитаем вероятность того, что количество уровней [math]h[/math] равно [math]k[/math].

[math]p(h = k) = 1 - p(h \gt k) - p(h \lt k)[/math].

[math]p(h \lt k) = (1 - p^{k})^n[/math], потому что вероятность того, что точка дойдёт до уровня [math]k[/math], равна [math]p^{k}[/math].

[math]p(h \gt k) = (1 - (1 - p^{k + 1})^n)[/math], потому что вероятность того, что точка не дойдёт до уровня [math]k + 1[/math], равна [math]1 - p^{k + 1}[/math].

[math]p(h = k) = 1 - p(h \gt k) - p(h \lt k) = 1 - (1 - (1 - p^{k + 1})^n) - (1 - p^{k})^n = (1 - p^{k + 1})^n - (1 - p^k)^n \leq 1 - (1 - p^k)^n \leq np^k[/math]

Теперь посчитаем мат. ожидание количества уровней:

[math]E(h) = \sum\limits_{k = 1}^{\infty} k \cdot p(h = k) = p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n + \sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k)[/math]

Оценим первую сумму:

[math]p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n \leq p(1) \cdot \log_{1/p} n + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n = O(\log(n))[/math], поскольку сумма этих вероятностей не превосходит единицу.

Оценим вторую сумму:

[math]\sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k) = \leq \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot n p^k = n \cdot \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k[/math]

Рассмотрим эту сумму:

[math]\sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k = p^{\log_{1/p} n} \cdot \sum\limits_{k = 0}^{\infty} (k + \log_{1/p} n) \cdot p^k = p^{\log_{1/p} n} \cdot (\sum\limits_{k = 0}^{\infty} (k p^k) + \log_{1/p} n \cdot \sum\limits_{k = 0}^{\infty} (p^k)) = p^{\log_{1/p} n} \cdot (O(1) + \log_{1/p} n \cdot O(1)) = 1/n \cdot O(\log(n))[/math]

Суммируя всё вышесказанное, получаем, что [math]O(\log(n))[/math].

Для лучшего понимания можно представлять, что [math]p = 1/2[/math].
[math]\triangleleft[/math]
Теорема (О времени работы):
Поиск, добавление и удаление точки работают за [math]O(\log(n))[/math] в среднем.
Доказательство:
[math]\triangleright[/math]
Напрямую следует из двух предыдущих лемм.
[math]\triangleleft[/math]
Теорема (О занимаемой памяти):
Математическое ожидание занимаемой памяти — [math]O(n)[/math].
Доказательство:
[math]\triangleright[/math]
Сжатое квадродерево для [math]n[/math] точек занимает [math]O(n)[/math] памяти. На нулевом уровне [math]n[/math] точек. На следующем уровне [math]p \cdot n[/math] точек, дальше [math]p^2 \cdot n[/math] и так далее. Получим геометрическую прогрессию, в итоге [math]O(n)[/math] памяти.
[math]\triangleleft[/math]

Запрос точек в прямоугольнике

Задача: нам дается прямоугольник, нужно выдать все точки, лежащие в нем.

Реализация запроса на сжатом квадродереве занимает [math]O(n)[/math] времени. Используем skip quadtree для ускорения поиска. Для этого ослабим условие задачи, тогда skip quadtree позволит очень быстро (асимптотически) отвечать на такие запросы.

Ослабление: расширим данный прямоугольник на [math]\varepsilon[/math]. Тогда в ответ могут попасть точки не из данного прямоугольника, но лежащие внутри [math]\varepsilon[/math]-области. В большинстве практических задач данное ослабление не ухудшит конечный результат, а только ускорит процесс.

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

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

Skip quadtree rect.png

Данный прямоугольник [math]R[/math] разбивает вершины на следующие классы:

  • [math]\mathrm{in}[/math]внутренние, то есть лежащие внутри [math]\varepsilon[/math]-области (1 и 6 на рисунке).
  • [math]\mathrm{out}[/math]внешние, то есть лежащие вне прямоугольника [math]R[/math] (2 на рисунке).
  • [math]\mathrm{stabbing}[/math]пронзающие, пересекающие [math]R[/math], но не являющиеся внутренними (3, 4 и 5 на рисунке).

Для вершин из классов [math]\mathrm{in}[/math] и [math]\mathrm{out}[/math] ответ на запрос находится тривиально — все поддерево вершины и никакие точки из поддерева соответственно; сложность представляют вершины из класса [math]\mathrm{stabbing}[/math]. Зная их все, мы можем ответить на запрос.

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

Назовем пронзающую вершину критической, если для каждого из ее детей выполняется одно из двух условий:

  • ребенок не является пронзающей вершиной.
  • ребенок является пронзающим, но содержит меньшую часть [math]E[/math], чем рассматриваемая вершина.

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

Вместо поиска всех пронзающих вершин, для решения задачи достаточно найти все критические вершины.

Лемма (Об упаковке):
Количество критических вершин на нулевом уровне дерева равно [math]O(\varepsilon^{-1})[/math].
Доказательство:
[math]\triangleright[/math]

Для квадратов с длиной стороны [math]\varepsilon[/math] верно, что они либо [math]\mathrm{in}[/math], либо [math]\mathrm{out}[/math], то есть [math]\mathrm{stabbing}[/math] вершин с такой стороной не бывает, как и со стороной меньше [math]\varepsilon[/math].

Все точки, содержащиеся в skip quadtree, находятся внутри какого-то прямоугольника, значит, длина его стороны — константа. Поэтому длина стороны области пересечения запрашиваемого прямоугольника со skip quadtree — это тоже константа. Тогда длина стороны запрашиваемого прямоугольника — [math]O(1)[/math].

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

Критических вершин не больше, чем пронзающих, так что их тоже [math]O(\varepsilon^{-1})[/math].
[math]\triangleleft[/math]

Алгоритм

Начинаем отвечать на запрос с корня [math]Q_0[/math] и определяем тип вершин.

  • Если вершина внутренняя, добавляем ее в ответ вместе с поддеревом.
  • Если внешняя, то игнорируем.
  • Если критическая, то рассмотрим всех ее детей.
  • Если не критическая, то найдем минимальную критическую, содержащую ту же часть [math]E[/math], что и рассматриваемая вершина.

Первые три варианта рассматриваются тривиально. Покажем, как для данной некритической вершины [math]p[/math] найти минимальную критическую вершину [math]q[/math], содержащую ту же часть [math]E[/math], что и [math]p[/math]. Для это найдем такое [math]Q_i[/math], что [math]p[/math] будет критической вершиной в [math]Q_i[/math] при максимальном [math]i[/math]. И будем действовать аналогично процессу локализации.

Таким образом, поиск [math]q[/math] займет [math]O(\log n)[/math] времени. А так как критических вершин всего [math]O(\varepsilon^{-1})[/math], то итоговая ассимптотика составит [math]O(\varepsilon^{-1} \cdot \log n + k)[/math].

Псевдокод

   void points_in_rectangle(rectangle R, rectangle E, vector<point>& points)
       queue<node> que
       que.push([math]Q_0[/math].root)
       while (!que.empty())
           node n = que.pop()
           rectangle K // прямоугольник, соответсвующий вершине n
           if (R [math]\cap[/math] K == [math]\varnothing[/math]) 
               continue
           else if (n is leaf)
               if (n.point in R)
                   points.push_back(n.point)
           else if (K [math]\subset[/math] E) 
               n.add_subtree(points) // добавляем все точки поддерева внутренней вершины
           else if (n is not critical)
               node q // некритическая вершина на максимальном уровне, соответствующая n
               level = k - 1 // максимальный уровень, на котором вершина q некритическая
               // k - количество уровней в skip quadtree
               while (level > 0)
                   node [math]n_{level}[/math] = n from [math]Q_{level}[/math] // вершина, соответствующая n в дереве [math]Q_{level}[/math]
                   if ([math]n_{level}[/math] != null and [math]n_{level}[/math] is not critical)
                       q = [math]n_{level}[/math]
                       break
                   level--
               while (true)
                   if (q is not critical)
                       node qc = ребенок q, содержащий ту же область E, что и q
                       if (qc is not leaf or level == 0)
                           q = qc
                       else if (level > 0)
                           level--
                           q = q from [math]Q_{level}[/math]
                   else if (level != 0)
                       level--
                       q = q from [math]Q_{level}[/math]
                   else 
                       break
               que.push(q)
           else
               que.add_all(n.children)

Источник