Изменения

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border''В списке билетов была опечатка, поэтому возникла путаница во многих местах. В этой статье оставляю просто всё полезное (и не очень) про квадродеревья, потому что нужно для скип-width: 1px;">Эта статья находится в разработке!</div><includeonly>[[Категория: В разработке]]</includeonly>квадродерева.''

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

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

Глубина квадродерева для множества точек <tex>P</tex> не превосходит <tex>log\log_2(s / c) + 31/2</tex>, где <tex>c</tex> {{---}} наименьшее расстояние между двумя точками из <tex>P</tex>, а <tex>s</tex> {{---}} сторона квадрата, с которого начинается построение квадродерева.

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

Каждая внутренняя вершина содержит хотя бы одну точку в соответствующем ей квадрате. Заметим, что квадраты с одного уровня не пересекаются и полностью покрывают весь исходный квадрат (в котором <tex>n</tex> точек). Значит, число внутренних вершин одного уровня не может первосходить превосходить <tex>n</tex>. Из этого следует, что всего внутренних вершин <tex>O(d \cdot n)</tex>.

При построении квадродерева наиболее длительная операция на каждом шаге {{---}} распределение точек по четвертям текущего квадрата. Таким образом, время, затрачиваемое на одну внутренню внутреннюю вершину, линейно зависит от числа точек в соответствующем ей квадрате. Как отмечалось выше, на одном уровне суммарно во всех внутренних вершинах не больше <tex>n</tex> точек, из чего следует доказываемая оценка.

[https://groups.google.com/forum/#!topic/uw.cs.cs240/MGfrsvKAiMA Тут] говорят, что работает за <tex>\theta Theta (d + n)</tex>. Видимо, так и есть, но я пока не понял, как это обосновать, может показаться, что <tex>\theta (d \cdot n)</tex>.Ну а вообще, можно делать по-тупому (без квадродерева, просто храня точки в списке или векторе) за <tex>O(n)</tex>, тупо проверяя все точки, но, видимо, так обычно на практике быстрее получается. Не очень понятно, используются ли вообще обычные квадродеревья кем-либо для этой цели.

''ВидимоНасчёт времени работы: понятно, что если какая-то вершина, попадающая в ответ, находится на дне дерева, то будет работать минимум за глубину. При этом месте заканчивается всё в ответе могут быть примерно все точки, поэтому будет работать минимум за <tex>\Theta(n)</tex>. Отсюда <tex>\Theta (d + n)</tex>. Поскольку вершин в дереве <tex>O(d \cdot n)</tex>, тоочевидно, что относится к данному билетубудет работать не дольше, чем <tex>O(d \cdot n)</tex>. Но, судя по всему, <tex>O(d + n)</tex> тоже верная оценка. Собственно, осталось доказать, далее идут просто полезные факты что <tex>O(сбалансированное упомянуто просто d + n)</tex> на запрос, и конспект готов. Короче, я не знаю, как это доказать, и мне кажется, что это не так. Если нам подали прямоугольник, содержащий все точки, то мы пройдём по всем вершинам, а сжатое нужно для первого билетакоторых <tex>O(d \cdot n)''</tex> (так написано в книжке, и лучшей оценки, видимо, нет). Возможно, я неправильно понимаю, что от нас хотят. Может быть, можно придумать какие-то оптимизации, ибо так совсем печальная оценка на запрос получается. Также могу предположить, что оценку времени можно улучшить, использовав функцию от размера ответа, но опять же не могу придумать/найти, как это сделать.

Тут можно ещё чтоОни нужны для каких-то написатьтам задач, но вроде это нам не нужнонужны, поэтому оставлю только определениеничего писать не буду.

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

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

Понятно, что любой квадрат <tex>p</tex>, содержащий хотя бы две точки, содержит единственный наибольший интересный квадрат. Сжатое квадродерево получается сжатием обычного таким образом, чтобы остались только интересные квадраты. Неинтересные квадраты расщепляются, и их пустые Пустые дети неинтересных квадратов удаляются. Для каждого интересного квадрата <tex>p</tex> будем хранить 4 указателя для каждой четверти этого квадрата. Если четверть содержит две или более точки, то указатель ссылается на наибольший интересный квадрат в этой четверти. Если четверть содержит одну точку, то указатель ссылается на эту точку. Наконец, если четверть не содержит точек, то указатель сделаем нулевым. Картинка проясняет ситуацию. Квадратикам соответствуют интересные квадраты, красным кружкам {{---}} точки, белым кружкам {{---}} пустота.

Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа внутренних вершин, каждая из которых является интересным квадратом (Кэп: то есть для числа интересных квадратов это надо доказать). Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше либо равно <tex>n</tex>:

* пусть в квадродереве доказано для квадродерева для <tex>n > - 1</tex> точек. Рассмотрим кореньДобавим новую точку <tex>x</tex>: сначала найдём наименьший интересный квадрат <tex>p(x)</tex>, у него обязательно должно быть хотя бы 2 непустых ребёнкакоторый её содержит. Если хотя бы один из детей является точкой<tex>x</tex> находится в его пустой четверти, то остальные непустые дети являются деревьямипросто добавляем <tex>x</tex> как лист, не изменив число интересных квадратов. Если же четверть <tex>p(x)</tex> в которых суммарно меньше которую необходимо вставить <tex>n - 1x</tex> точек. Значит, в них суммарно меньше уже содержит точку <tex>n - 1y</tex> интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве меньше или интересный квадрат <tex>nr</tex> интересных квадратов. Если же все непустые дети корня являются интересными квадратами), то мы всё ранво можем применить индукционное предположение ко всем детям и получить то же самоедобавить в дерево интересный квадрат, поскольку во всех поддеревьях который будет меньше содержать <tex>nx</tex> точек (ибо их суммарно и <tex>ny</tex> и везде есть хотя бы однав разных четвертях. Таким образом, при добавлении точки мы увеличиваем количество интересных квадратов не более, так как дети непустые)чем на один. Таким образом, квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин. Глубина, очевидно, тоже <tex>O(n)</tex>, поскольку на каждом уровне есть хотя бы одна вершина (Кэпздесь под вершинами имеются в виду узлы в дереве). При этом лучшей оценки получше нет (то есть глубина <tex>\thetaTheta(n)</tex>). На картинке в правом дереве можно на место левого нижнего красного кружка поставить опять такое дерево и так делать сколь угодно долго, получим высоту глубину <tex>\thetaTheta(n)</tex>.

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

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

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

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