170
правок
Изменения
Нет описания правки
Если совсем кратко, то запрос выглядит так:
<code>
QTree-RangeSearch(P, M):
if (P is a leaf) then
if (P.point in M) then
[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>, но, видимо, так обычно быстрее получается.
== Сбалансированное квадродерево ==
Квадродерево называется '''сбалансированным''', если для соответствующего ему разбиения плоскости на квадраты верно, что для любых двух соседних квадратов их стороны отличаются не более чем в два раза.
Тут можно ещё что-то написать, но вроде это не нужно, поэтому оставлю только определение.
== Сжатое квадродерево ==
Обычное квадродерево может иметь слишком большую глубину независимо от количества точек. Сжатое дерево лишено данного недостатка, имеет глубину <tex>O(n)</tex>, и на его основе строится [[Skip quadtree: определение, время работы | Skip Quadtree]].
Назовём квадрат интересным, если соответствующая ему вершина дерева имеет хотя бы 2 непустых ребёнка (то есть таких, что в их квадратах содержится хотя бы одна точка) или является корнем. Понятно, что любой квадрат <tex>p</tex>, содержащий хотя бы две точки, содержит единственный наибольший интересный квадрат.
== Литература ==
* ''van Kreveld, de Berg, Overmars, Cheong {{---}} Computational Geometry. Algorithms and Applications.'' Страница 309.Тут можно почитать про квадродеревья.* [http://arxiv.org/pdf/cs.cg/0507049.pdf Статья на архиве про Skip Quadtree] Тут можно почитать про сжатое квадродерево.* [http://en.wikipedia.org/wiki/Quadtree Квадродерево на Википедии]* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D0%BD%D1%82%D0%BE%D0%B2 Даже на русский переведено, оказывается]
