Квадродеревья

Эта статья находится в разработке!

Определение и построение

Квадродерево — дерево, каждая внутренняя вершина которого содержит 4 ребёнка. Любому узлу квадродерева соответствует некоторый квадрат. Если внутренней вершине [math]v[/math] соответствует какой-то квадрат [math]a[/math], то её детям соответствуют четверти квадрата [math]a[/math] (см. картинку).

По картинке должно быть понятно

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

Пусть дано множество точек [math]P[/math], для которого нужно построить квадродерево. Начнём с некоторого квадрата [math]\sigma[/math], содержащего все точки из [math]P[/math]. Если он не дан явно, его можно легко найти за линейное время от числа вершин. Пусть [math]\sigma = [x_0, x_1] \times [y_0, y_1][/math]. Обозначим [math]x_m = (x_0 + x_1) / 2; y_m = (y_0 + y_1) / 2[/math]. Тогда:

• если [math]P[/math] содержит не больше одной точки, то квадродерево состоит из одного листа, которому соответствует квадрат [math]\sigma[/math];
• иначе корнем дерева делаем вершину [math]v[/math], которой соответствует квадрат [math]\sigma[/math], а его дети — [math]v_{NE}, v_{NW}, v_{SW}, v_{SE}[/math], и им соответствуют квадраты [math]\sigma_{NE} = (x_m, x_1] \times (y_m, y_1][/math], [math]\sigma_{NW} = [x_0, x_m] \times (y_m, y_1][/math], [math]\sigma_{SW} = [x_0, x_m] \times [y_0, y_m][/math], [math]\sigma_{SE} = (x_m, x_1] \times [y_0, y_m][/math]. Затем таким же образом рекурсивно превращаем каждого ребёнка в квадродерево для множества точек, лежащих в соответствующем квадрате.

Леммы и теоремы

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

Лемма:

Глубина квадродерева для множества точек [math]P[/math] не превосходит [math]log(s / c) + 3/2[/math], где [math]c[/math] — наименьшее расстояние между двумя точками из [math]P[/math], а [math]s[/math] — сторона квадрата, с которого начинается построение квадродерева.

Доказательство:

[math]\triangleright[/math]

Сторона квадрата на глубине [math]i[/math], очевидно, равна [math]s / 2^i[/math]. Максимальное расстояние между двумя точками внутри квадрата достигается, когда они являются вершинами диагонали, то есть на глубине [math]i[/math] расстояние между любыми двумя точками в одном квадрате не превосходит [math]s \sqrt 2 / 2^i[/math]. Поскольку внутренняя вершина квадродерева содержит хотя бы 2 точки в соответствующем ей квадрате, то [math]s \sqrt 2 / 2^i \geq c[/math], так как [math]c[/math] — минимальное расстояние между точками в [math]P[/math]. Отсюда следует, что [math]i \leq log(s \sqrt 2 / c) = log (s / c) + 1/2[/math]. Значит, глубина любой внутренней вершины не превосходит [math]log (s / c) + 1/2[/math], из чего следует утверждение леммы.

[math]\triangleleft[/math]

Размер дерева и время построения будут также зависеть и от [math]n[/math] — мощности [math]P[/math].

Теорема:

Квадродерево глубины [math]d[/math] для [math]n[/math] точек содержит [math]O(d \cdot n)[/math] вершин и может быть построено за [math]O(d \cdot n)[/math].

Доказательство:

[math]\triangleright[/math]

Поскольку каждая внутренняя вершина имеет четырёх детей, то суммарное число листьев будет [math]3i + 1[/math], где [math]i[/math] — число внутренних вершин. Поэтому достаточно доказать оценки лишь для внутренних вершин. Каждая внутренняя вершина содержит хотя бы одну точку в соответствующем ей квадрате. Заметим, что квадраты с одного уровня не пересекаются и полностью покрывают весь исходный квадрат (в котором [math]n[/math] точек). Значит, число внутренних вершин одного уровня не может первосходить [math]n[/math]. Из этого следует, что всего внутренних вершин [math]O(d \cdot n)[/math]. При построении квадродерева наиболее длительная операция на каждом шаге — распределение точек по четвертям текущего квадрата. Таким образом, время, затрачиваемое на одну внутренню вершину, линейно зависит от числа точек в соответствующем ей квадрате. Как отмечалось выше, на одном уровне суммарно во всех внутренних вершинах не больше [math]n[/math] точек, из чего следует доказываемая оценка.

[math]\triangleleft[/math]

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

Пусть на вход подаётся некоторый прямоугольник [math]M[/math], для которого надо вернуть все точки из множества [math]P[/math], которые принадлежат этому прямоугольнику.

Алгоритм следующий:

• если мы лист, то просто проверяем, лежит ли наша точка в [math]M[/math], и возвращаем её, если да;
• иначе запускаемся от детей и возвращаем объединение всего того, что вернули дети.

Псевдокод можно посмотреть здесь. Там немного по-другому (хранят не больше 4-х точек в каждой вершине дерева, а у нас подразумевается, что точки явно хранятся только в листьях), но в целом [math]queryRange[/math] почти такой же.

Если совсем кратко, то запрос выглядит так:

QTree-RangeSearch(P, M):
 if (P is a leaf) then
         if (P.point in M) then
                  report P.point
 for each child C of P do
         if C.region intersects M then
                 QTree-RangeSearch(C, M)

Тут говорят, что работает за [math]\theta (d + n)[/math]. Видимо, так и есть, но я пока не понял, как это обосновать, может показаться, что [math]\theta (d \cdot n)[/math]. Ну а вообще, можно делать по-тупому за [math]O(n)[/math], но, видимо, так обычно быстрее получается.

Видимо, в этом месте заканчивается всё то, что относится к данному билету, далее идут просто полезные факты (сбалансированное упомянуто просто так, а сжатое нужно для первого билета)

Сбалансированное квадродерево

Квадродерево называется сбалансированным, если для соответствующего ему разбиения плоскости на квадраты верно, что для любых двух соседних квадратов их стороны отличаются не более чем в два раза.

Тут можно ещё что-то написать, но вроде это не нужно, поэтому оставлю только определение.

Сжатое квадродерево

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

Назовём квадрат интересным, если соответствующая ему вершина дерева имеет хотя бы 2 непустых ребёнка (то есть таких, что в их квадратах содержится хотя бы одна точка) или является корнем. Понятно, что любой квадрат [math]p[/math], содержащий хотя бы две точки, содержит единственный наибольший интересный квадрат.

Пример сжатого квадродерева (справа сжатая версия левого)

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

О размерах сжатого квадродерева

Лемма:

Сжатое квадродерево для [math]n[/math] точек имеет [math]O(n)[/math] вершин и глубину [math]O(n)[/math].

Доказательство:

[math]\triangleright[/math]

Как отмечалось в представленной выше теореме, достаточно доказать оценку [math]O(n)[/math] для числа внутренних вершин, каждая из которых является интересным квадратом (Кэп: то есть для числа интересных квадратов это надо доказать). Докажем по индукции, что в квадродереве для [math]n[/math] точек количество интересных квадратов меньше [math]n[/math]: для [math]n = 1[/math] это очевидно; пусть в квадродереве [math]n \gt 1[/math] точек. Рассмотрим корень, у него обязательно должно быть хотя бы 2 непустых ребёнка. Если хотя бы один из детей является точкой, то остальные непустые дети являются деревьями, в которых суммарно меньше [math]n - 1[/math] точек. Значит, в них суммарно меньше [math]n - 1[/math] интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве меньше [math]n[/math] интересных квадратов. Если же все непустые дети корня являются интересными квадратами, то мы всё ранво можем применить индукционное предположение ко всем детям и получить то же самое, поскольку во всех поддеревьях будет меньше [math]n[/math] точек (ибо их суммарно [math]n[/math] и везде есть хотя бы одна, так как дети непустые). Таким образом, квадродерево для [math]n[/math] точек имеет [math]O(n)[/math] вершин. Глубина, очевидно, тоже [math]O(n)[/math], поскольку на каждом уровне есть хотя бы одна вершина (Кэп). При этом лучшей оценки нет (то есть глубина [math]\theta(n)[/math]). На картинке в правом дереве можно на место левого нижнего красного кружка поставить опять такое дерево и так делать сколь угодно долго, получим высоту [math]\theta(n)[/math].

[math]\triangleleft[/math]

Операции над сжатым квадродеревом

Все операции похожи на аналогичные в обычных деревьях поиска. Только они делаются за [math]O(n)[/math]. Того же самого можно добиться тупым перебором. Хотя на практике, наверно, так побыстрее. Но всё же сама по себе структура не особо полезна, зато пополезнее будет Skip Quadtree.

Поиск

Нам дают точку, хотим найти наименьший интересный квадрат, который её содержит. Довольно очевидно, как это делать: просто идём вниз по дереву в нужную четверть, начиная с корня. В какой-то момент закончим, найдя наименьший интересный квадрат, который содержит искомую точку. Дальше легко проверить, есть ли такая точка в квадродереве. Работает, очевидно, за высоту, которая линейно зависит от числа точек (см. выше).

Вставка

Сначала запускаем поиск, находим наименьший квадрат, в который надо вставиться, понимаем, в какую четверть вставляться. Если она пустая, то всё совсем просто, меняем 1 указатель. Если там что-то есть, то добавим новый интересный квадрат, поправим [math]O(1)[/math] указателей, и всё хорошо. Опять же [math]O(n)[/math] (потому что поиск столько длится).

Удаление

Начнём, разумеется, с поиска. Если такая точка есть, то обнулим поинтер на неё, при этом квадрат, который был интересный, может больше не быть интересным. При этом родитель этого квадрата всё равно останется интересным. Значит, в таком случае просто заменим этот квадрат на точку. В общем, тут тоже [math]O(n)[/math] (потому что поиск столько длится).

Литература

• van Kreveld, de Berg, Overmars, Cheong — Computational Geometry. Algorithms and Applications. Страница 309. Тут можно почитать про квадродеревья.
• Статья на архиве про Skip Quadtree Тут можно почитать про сжатое квадродерево.
• Квадродерево на Википедии
• Даже на русский переведено, оказывается