Квадродеревья — различия между версиями
Gromak (обсуждение | вклад) (Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...») |
(нет различий)
|
Версия 13:06, 5 января 2014
Определение и построение
Квадродерево — дерево, каждая внутренняя вершина которого содержит 4 ребёнка. Любому узлу квадродерева соответствует некоторый квадрат. Если внутренней вершине
соответствует какой-то квадрат , то её детям соответствуют четверти квадрата (см. картинку).Вообще говоря, квадродеревья могут быть использованы для разных целей и хранить разные данные, но нам они нужны для перечисления точек в произвольном прямоугольнике, соответственно, хранить в них будем какой-то набор точек.
Пусть дано множество точек
, для которого нужно построить квадродерево. Начнём с некоторого квадрата , содержащего все точки из . Если он не дан явно, его можно легко найти за линейное время от числа вершин. Пусть . Обозначим . Тогда:- если содержит не больше одной точки, то квадродерево состоит из одного листа, которому соответствует квадрат ;
- иначе корнем дерева делаем вершину , которой соответствует квадрат , а его дети — , и им соответствуют квадраты , , , . Затем таким же образом рекурсивно превращаем каждого ребёнка в квадродерево для множества точек, лежащих в соответствующем квадрате.
Леммы и теоремы
Сперва оценим глубину квадродерева. Если какие-то две точки лежат очень близко, то процесс построения может продолжаться очень долго, поэтому глубину невозможно оценить функцией от числа вершин.
Лемма: |
Глубина квадродерева для множества точек не превосходит , где — наименьшее расстояние между двумя точками из , а — сторона квадрата, с которого начинается построение квадродерева. |
Доказательство: |
Сторона квадрата на глубине | , очевидно, равна . Максимальное расстояние между двумя точками внутри квадрата достигается, когда они являются вершинами диагонали, то есть на глубине расстояние между любыми двумя точками в одном квадрате не превосходит . Поскольку внутренняя вершина квадродерева содержит хотя бы 2 точки в соответствующем ей квадрате, то , так как — минимальное расстояние между точками в . Отсюда следует, что . Значит, глубина любой внутренней вершины не превосходит , из чего следует утверждение леммы.
Размер дерева и время построения будут также зависеть и от
— мощности .Теорема: |
Квадродерево глубины для точек содержит вершин и может быть построено за . |
Доказательство: |
Поскольку каждая внутренняя вершина имеет четырёх детей, то суммарное число листьев будет Каждая внутренняя вершина содержит хотя бы одну точку в соответствующем ей квадрате. Заметим, что квадраты с одного уровня не пересекаются и полностью покрывают весь исходный квадрат (в котором , где — число внутренних вершин. Поэтому достаточно доказать, что внутренних вершин . точек). Значит, число внутренних вершин одного уровня не может первосходить . Из этого следует, что всего внутренних вершин . |
Литература
- van Kreveld, de Berg, Overmars, Cheong — Computational Geometry. Algorithms and Applications. Страница 309.