170
правок
Изменения
Нет описания правки
Локализация выполняется аналогично сжатому квадродереву. Под локализацией под разумевается, что мы хотим найти минимальный интересный квадрат задержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далее, пока не дойдём до дна.
Для добавления сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно увеличиться максимум на 1, то есть, если появился новый уровень, то процесс точно заканчивается. Хотя не, давайте без последнего условия, вроде с ним только лучше, но без него проще доказывать.
Удаление совсем просто: локализуемся, удаляем со всех уровней, на которых есть.
== Время работы и память ==
{{Лемма
О количестве шагов на одном уровне
|statement=
На каждом уровне в среднем совершается <tex>O(1)</tex> шагов поиска для любой точки <tex>x</tex>.
|proof=
Пусть в <tex>Q_i</tex> (то есть на <tex>i</tex>-ом уровне) поиск точки <tex>x</tex>, начинающийся с корня, проходит по квадратам <tex>p_0, p_1, \dots, p_m</tex>. Пусть случайная величина <tex>j</tex> {{---}} количество шагов поиска в <tex>Q_i</tex>, тогда <tex>p_{m - j}</tex> {{---}} последний квадрат из <tex>p_0, p_1, \dots, p_m</tex>, являющийся интересным в <tex>Q_{i + 1}</tex>.
<tex>E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)}) \leq \sum\limits_{j = 1}^{\infty} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)})</tex>
В общем, если так подумать, это <tex>O(1)</tex>. Мне пока весьма лень совсем строго написать, но вообще и так понятно. Разумеется, при условии <tex>p \in (0, 1)</tex>. Это почти геометрическая прогрессия, только на полином домножили.
}}
{{Лемма
|about=
О количестве уровней
|statement=
Математическое ожидание количества уровней составляет <tex>O(log(n))</tex>
|proof=
Патак.
}}
{{Теорема
|about=
О времени работы
|statement=
Поиск, добавление и удаление точки работают за <tex>O(log(n))</tex> в среднем.
|proof=
Достаточно очевидно из предыдущих лемм.
}}
{{Теорема
|about=
О занимаемой памяти
|statement=
Математическое ожидание занимаемой памяти {{---}} <tex>O(n)</tex>.
|proof=
Сжатое квадродерево для <tex>n</tex> точек занимает <tex>O(n)</tex> памяти. На нулевом уровне <tex>n</tex> точек. На следующем уровне <tex>p \cdot n</tex> точек, дальше <tex>p^2 \cdot n</tex> и так далее. Получим геометрическую прогрессию, в итоге <tex>O(n)</tex> памяти.
}}
== Источник ==
http://arxiv.org/pdf/cs.cg/0507049.pdf
