25
правок
Изменения
Нет описания правки
Каждая из этих областей будет одним из листов КД-дерева. Для построения всего дерева сначала объединим все области для одной вертикальной полосы, сливая соседние области в одну вершину. После этого аналогично будем сливать соседние вертикальные области и в итоге получим корневую вершину, представляющую всю плоскость.
Построенное КД-дерево обладает следующими свойствами:# В нем <tex>O(n)</tex> областейвершин.
# Каждый прямоугольник хранится в <tex>O(\sqrt{n})</tex> листьях.
# Каждый прямоугольник влияет на <tex>O(\sqrt{n} \log n)</tex> значений <tex>Cover</tex>.
Каждая операция добавления или удаления прямоугольников требует изменения <tex>O(\sqrt{n} \log n)</tex> полей <tex>Cover</tex>, а также операций добавления или удаления прямоугольника в <tex>O(\sqrt{n})</tex> листьев, каждая из которых требует <tex>O(\log n)</tex> времени. Итого, на одну операцию добавления или удаления требуется <tex>O(\sqrt{n} \log n)</tex> времени, суммарно таких операций <tex>O(n)</tex>, и получается, что весь алгоритм работает за <tex>O(n \sqrt{n} \log n)</tex>. При этом на хранение всей информации требуется <tex>O(n\sqrt{n}) </tex> памяти - каждый лист может хранить <tex>O(\sqrt{n})</tex> прямоугольников.
Все идеи этого алгоритма обобщаются с трехмерного пространства на <tex>d</tex>-мерное следующим образом.
Построение разбиения на области в <tex>d</tex>-мерном пространстве вместо двухмерного ведется сначала аналогичным образом, только после того, как в двухмерном пространстве получаются итоговые прямоугольные области, здесь продолжаются аналогичные разбиения вдоль третьей координаты - берутся все границы третьей координаты гиперпараллелепипедов, имеющие границу по первой или второй координате строго внутри области (их получается не более <tex>O(\sqrt{n})</tex>), а также каждую <tex>O(\sqrt{n})</tex>-ую границу по третьей координате гиперепараллелепипедов, пересекающих эту область, и так далее.
Это разбиение на области имеет следующие аналогичные свойства:
# Всего <tex>O(n^{d/2})</tex> областей.
# Каждый гиперпараллелепипед частично покрывает не более <tex>O(n^{(d-1)/2})</tex> областей.
# Никакая вершина гиперпараллелепипеда не лежит внутри какой-нибудь области.
# Для каждой области есть не более <tex>O(\sqrt{n})</tex> частично покрывающих ее гиперпараллелепипедов.
Общее дерево строится аналогичным образом и оно в итоге состоит из <tex>d</tex> уровней, каждый из которых имеет высоту <tex>O(\log n)</tex> в дереве - самый верхний уровень содержит разбиение по первой координате, следующий - по второй и так далее.
Построенное КД-дерево обладает следующими свойствами:
# В нем <tex>O(n^{d/2})</tex> вершин.
# Каждый гиперпараллелепипед хранится в <tex>O(n^{(d-1)/2})</tex> листьях.
# Каждый гиперпараллелепипед влияет на <tex>O(n^{(d-1)/2} \log n)</tex> значений <tex>Cover</tex>.
# Никакая вершина гиперпараллелепипеда не лежит внутри области какого-нибудь листа.
# Для области каждого листа есть не более <tex>O(\sqrt{n})</tex> частично покрывающих ее гиперпараллелепипедов.
Операции в этом дереве выполняются аналогично трехмерному случаю и каждая операция добавления или удаления в КД-дерево размерности <tex>d</tex> занимает <tex>O(n^{(d-1)/2} \log n)</tex> времени. Выполняя сканирование гиперплоскостью вдоль одной из координат получаем КД-дерево размерности <tex>d-1</tex>, в котором необходимо провести <tex>O(n)</tex> операций, то есть суммарное время работы алгоритма равно: <tex>O(n \times n^{(d-1-1)/2} \log n) = O(n^{d/2} \log n)</tex>. При этом хранение КД-дерева требует <tex>O(n^{d/2})</tex> памяти.
