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

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

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

Квадродерево — дерево, каждая внутренняя вершина которого содержит 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_2(s / c) + 1/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_2(s \sqrt 2 / c) = \log_2 (s / c) + 1/2[/math]. Значит, глубина любой внутренней вершины не превосходит [math]\log_2 (s / c) + 1/2[/math], из чего следует утверждение леммы (так как самый глубокий лист лежит на 1 глубже самой глубокой внутренней вершины).

[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]O(n)[/math], тупо проверяя все точки, но, видимо, так на практике быстрее получается. Не очень понятно, используются ли вообще обычные квадродеревья кем-либо для этой цели.

Насчёт времени работы: понятно, что если какая-то вершина, попадающая в ответ, находится на дне дерева, то будет работать минимум за глубину. При этом в ответе могут быть примерно все точки, поэтому будет работать минимум за [math]\Theta(n)[/math]. Отсюда [math]\Theta (d + n)[/math]. Поскольку вершин в дереве [math]O(d \cdot n)[/math], то очевидно, что будет работать не дольше, чем [math]O(d \cdot n)[/math]. Но, судя по всему, [math]O(d + n)[/math] тоже верная оценка.

Собственно, осталось доказать, что [math]O(d + n)[/math] на запрос, и конспект готов.

Короче, я не знаю, как это доказать, и мне кажется, что это не так. Если нам подали прямоугольник, содержащий все точки, то мы пройдём по всем вершинам, которых [math]O(d \cdot 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 - 1[/math] точек. Добавим новую точку [math]x[/math]: сначала найдём наименьший интересный квадрат [math]p(x)[/math], который её содержит. Если [math]x[/math] находится в его пустой четверти, то просто добавляем [math]x[/math] как лист, не изменив число интересных квадратов. Если же четверть [math]p(x)[/math] в которую необходимо вставить [math]x[/math], уже содержит точку [math]y[/math]( или интересный квадрат [math]r[/math]), то мы можем добавить в дерево интересный квадрат, который будет содержать [math]x[/math] и [math]y[/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(1)[/math] действий.

Удаление

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

Литература

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