Изменения

* иначе корнем дерева делаем вершину <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>. Затем таким же образом рекурсивно превращаем каждого ребёнка в квадродерево для множества точек, лежащих в соответствующем квадратесоответствующих четвертях.

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