170
правок
Изменения
Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>
== Определение и построение ==
'''Квадродерево''' {{---}} дерево, каждая внутренняя вершина которого содержит 4 ребёнка. Любому узлу квадродерева соответствует некоторый квадрат. Если внутренней вершине <tex>v</tex> соответствует какой-то квадрат <tex>a</tex>, то её детям соответствуют четверти квадрата <tex>a</tex> (см. картинку).
[[Файл:Quadtree.png | 500px | thumb | По картинке должно быть понятно]]
Вообще говоря, квадродеревья могут быть использованы для разных целей и хранить разные данные, но нам они нужны для перечисления точек в произвольном прямоугольнике, соответственно, хранить в них будем какой-то набор точек.
Пусть дано множество точек <tex>P</tex>, для которого нужно построить квадродерево. Начнём с некоторого квадрата <tex>\sigma</tex>, содержащего все точки из <tex>P</tex>. Если он не дан явно, его можно легко найти за линейное время от числа вершин. Пусть <tex>\sigma = [x_0, x_1] \times [y_0, y_1]</tex>. Обозначим <tex>x_m = (x_0 + x_1) / 2; y_m = (y_0 + y_1) / 2</tex>. Тогда:
* если <tex>P</tex> содержит не больше одной точки, то квадродерево состоит из одного листа, которому соответствует квадрат <tex>\sigma</tex>;
* иначе корнем дерева делаем вершину <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>. Затем таким же образом рекурсивно превращаем каждого ребёнка в квадродерево для множества точек, лежащих в соответствующем квадрате.
== Леммы и теоремы ==
Сперва оценим глубину квадродерева. Если какие-то две точки лежат очень близко, то процесс построения может продолжаться очень долго, поэтому глубину невозможно оценить функцией от числа вершин.
{{Лемма
|statement=
Глубина квадродерева для множества точек <tex>P</tex> не превосходит <tex>log(s / c) + 3/2</tex>, где <tex>c</tex> {{---}} наименьшее расстояние между двумя точками из <tex>P</tex>, а <tex>s</tex> {{---}} сторона квадрата, с которого начинается построение квадродерева.
|proof=
Сторона квадрата на глубине <tex>i</tex>, очевидно, равна <tex>s / 2^i</tex>. Максимальное расстояние между двумя точками внутри квадрата достигается, когда они являются вершинами диагонали, то есть на глубине <tex>i</tex> расстояние между любыми двумя точками в одном квадрате не превосходит <tex>s \sqrt 2 / 2^i</tex>. Поскольку внутренняя вершина квадродерева содержит хотя бы 2 точки в соответствующем ей квадрате, то <tex>s \sqrt 2 / 2^i \geq c</tex>, так как <tex>c</tex> {{---}} минимальное расстояние между точками в <tex>P</tex>. Отсюда следует, что <tex>i \leq log(s \sqrt 2 / c) = log (s / c) + 1/2</tex>. Значит, глубина любой внутренней вершины не превосходит <tex>log (s / c) + 1/2</tex>, из чего следует утверждение леммы.
}}
Размер дерева и время построения будут также зависеть и от <tex>n</tex> {{---}} мощности <tex>P</tex>.
{{Теорема
|statement=
Квадродерево глубины <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>.
}}
== Литература ==
* ''van Kreveld, de Berg, Overmars, Cheong {{---}} Computational Geometry. Algorithms and Applications.'' Страница 309.
<includeonly>[[Категория: В разработке]]</includeonly>
== Определение и построение ==
'''Квадродерево''' {{---}} дерево, каждая внутренняя вершина которого содержит 4 ребёнка. Любому узлу квадродерева соответствует некоторый квадрат. Если внутренней вершине <tex>v</tex> соответствует какой-то квадрат <tex>a</tex>, то её детям соответствуют четверти квадрата <tex>a</tex> (см. картинку).
[[Файл:Quadtree.png | 500px | thumb | По картинке должно быть понятно]]
Вообще говоря, квадродеревья могут быть использованы для разных целей и хранить разные данные, но нам они нужны для перечисления точек в произвольном прямоугольнике, соответственно, хранить в них будем какой-то набор точек.
Пусть дано множество точек <tex>P</tex>, для которого нужно построить квадродерево. Начнём с некоторого квадрата <tex>\sigma</tex>, содержащего все точки из <tex>P</tex>. Если он не дан явно, его можно легко найти за линейное время от числа вершин. Пусть <tex>\sigma = [x_0, x_1] \times [y_0, y_1]</tex>. Обозначим <tex>x_m = (x_0 + x_1) / 2; y_m = (y_0 + y_1) / 2</tex>. Тогда:
* если <tex>P</tex> содержит не больше одной точки, то квадродерево состоит из одного листа, которому соответствует квадрат <tex>\sigma</tex>;
* иначе корнем дерева делаем вершину <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>. Затем таким же образом рекурсивно превращаем каждого ребёнка в квадродерево для множества точек, лежащих в соответствующем квадрате.
== Леммы и теоремы ==
Сперва оценим глубину квадродерева. Если какие-то две точки лежат очень близко, то процесс построения может продолжаться очень долго, поэтому глубину невозможно оценить функцией от числа вершин.
{{Лемма
|statement=
Глубина квадродерева для множества точек <tex>P</tex> не превосходит <tex>log(s / c) + 3/2</tex>, где <tex>c</tex> {{---}} наименьшее расстояние между двумя точками из <tex>P</tex>, а <tex>s</tex> {{---}} сторона квадрата, с которого начинается построение квадродерева.
|proof=
Сторона квадрата на глубине <tex>i</tex>, очевидно, равна <tex>s / 2^i</tex>. Максимальное расстояние между двумя точками внутри квадрата достигается, когда они являются вершинами диагонали, то есть на глубине <tex>i</tex> расстояние между любыми двумя точками в одном квадрате не превосходит <tex>s \sqrt 2 / 2^i</tex>. Поскольку внутренняя вершина квадродерева содержит хотя бы 2 точки в соответствующем ей квадрате, то <tex>s \sqrt 2 / 2^i \geq c</tex>, так как <tex>c</tex> {{---}} минимальное расстояние между точками в <tex>P</tex>. Отсюда следует, что <tex>i \leq log(s \sqrt 2 / c) = log (s / c) + 1/2</tex>. Значит, глубина любой внутренней вершины не превосходит <tex>log (s / c) + 1/2</tex>, из чего следует утверждение леммы.
}}
Размер дерева и время построения будут также зависеть и от <tex>n</tex> {{---}} мощности <tex>P</tex>.
{{Теорема
|statement=
Квадродерево глубины <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>.
}}
== Литература ==
* ''van Kreveld, de Berg, Overmars, Cheong {{---}} Computational Geometry. Algorithms and Applications.'' Страница 309.
