170
правок
Изменения
Нет описания правки
Квадродерево глубины <tex>d</tex> для <tex>n</tex> точек содержит <tex>O(d \cdot n)</tex> вершин и может быть построено за <tex>O(d \cdot n)</tex>.
|proof=
Поскольку каждая внутренняя вершина имеет четырёх детей, то суммарное число листьев будет <tex>3i + 1</tex>, где <tex>i</tex> {{---}} число внутренних вершин. Поэтому достаточно доказать, что оценки лишь для внутренних вершин <tex>O(d \cdot n)</tex>.
Каждая внутренняя вершина содержит хотя бы одну точку в соответствующем ей квадрате. Заметим, что квадраты с одного уровня не пересекаются и полностью покрывают весь исходный квадрат (в котором <tex>n</tex> точек). Значит, число внутренних вершин одного уровня не может первосходить <tex>n</tex>. Из этого следует, что всего внутренних вершин <tex>O(d \cdot n)</tex>.
При построении квадродерева наиболее длительная операция на каждом шаге {{---}} распределение точек по четвертям текущего квадрата. Таким образом, время, затрачиваемое на одну внутренню вершину, линейно зависит от числа точек в соответствующем ей квадрате. Как отмечалось выше, на одном уровне суммарно во всех внутренних вершинах не больше <tex>n</tex> точек, из чего следует доказываемая оценка.
}}
== Перечисление точек в произвольном прямоугольнике ==
Пусть на вход подаётся некоторый прямоугольник <tex>M</tex>, для которого надо вернуть все точки из множества <tex>P</tex>, которые принадлежат этому прямоугольнику.
Алгоритм следующий:
* если мы лист, то просто проверяем, лежит ли наша точка в <tex>M</tex>, и возвращаем её, если да;
* иначе запускаемся от детей и возвращаем объединение всего того, что вернули дети.
Псевдокод можно посмотреть [http://en.wikipedia.org/wiki/Quadtree#Pseudo_code здесь]. Там немного по-другому (хранят не больше 4-х точек в каждой вершине дерева, а у нас подразумевается, что точки явно хранятся только в листьях), но в целом <tex>queryRange</tex> почти такой же.
Если совсем кратко, то запрос выглядит так:
<code>
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)
</code>
[https://groups.google.com/forum/#!topic/uw.cs.cs240/MGfrsvKAiMA Тут] говорят, что работает за <tex>\theta (d + n)</tex>. Видимо, так и есть, но я пока не понял, как это обосновать, может показаться, что <tex>\theta (d \cdot n)</tex>.
Ну а вообще, можно делать по-тупому за <tex>O(n)</tex>, но, видимо, так обычно быстрее получается.
== Литература ==
* ''van Kreveld, de Berg, Overmars, Cheong {{---}} Computational Geometry. Algorithms and Applications.'' Страница 309.
