25
правок
Изменения
Нет описания правки
Аналогично устроена операция удаления прямоугольника - она выполняет обратные действия.
Рассмотрим теперь как именно будет устроено разделение пространства на области КД-деревом для эффективного его использования.
Возьмем проекции всех параллелепипедов на плоскость, перепендикулярную оси <tex>OZ</tex> - множество прямоугольников <tex>V</tex>. Рассмотрим все <tex>x</tex>-координаты границ прямоугольников и разобьем ось <tex>OX</tex> на <tex>2\sqrt{n}</tex> промежутков так, чтобы в каждом из них было не более <tex>\sqrt{n}</tex> границ. Получившиемя <tex>2\sqrt{n}</tex> полос разобьем горизонтальными линиями на итоговые области по отдельности следующим образом. Для каждой полосы у всех прямоугольников, имеющих вертикальную границу в этой полосе возьмем все горизонтальные границы (их будет не более <tex>2\sqrt{n}</tex>), а среди всех горизонтальных границ, пересекающих область, возьмем каждую <tex>\sqrt{n}</tex>-ую. Таким образом, в итоге получим не более <tex>4\sqrt{n}</tex> областей в каждой верикальной полосе.
Полученные области обладают следующими свойствами:
# Всего <tex>O(n)</tex> областей.
# Каждый прямоугольник частично покрывает не более <tex>O(\sqrt{n})</tex> областей.
# Никакая вершина прямоугольника не лежит внутри какой-нибудь области.
# Для каждой области есть не более <tex>O(\sqrt{n})</tex> частично покрывающих ее прямоугольников.
Все эти утверждения несложно следуют из алгоритма разбиения на области.
Каждая из этих областей будет одним из листов КД-дерева. Для построения всего дерева сначала объединим все области для одной вертикальной полосы, сливая соседние области в одну вершину. После этого аналогично будем сливать соседние вертикальные области и в итоге получим корневую вершину, представляющую всю плоскость.
Построенное дерево обладает следующими свойствами:
# В нем <tex>O(n)</tex> областей.
# Каждый прямоугольник хранится в <tex>O(\sqrt{n})</tex> листьях.
# Каждый прямоугольник влияет на <tex>O(\sqrt{n} \log n)</tex> значений <tex>Cover</tex>.
# Никакая вершина прямоугольника не лежит внутри области какого-нибудь листа.
# Для области каждого листа есть не более <tex>O(\sqrt{n})</tex> частично покрывающих ее прямоугольников.
Все эти свойства следуют из свойств разбиения на области и логарифмической высоты дерева.
Наконец, получаем итоговый алгоритм. Идем сканирующей плоскостью, перепендикулярной оси <tex>OZ</tex>, добавляя или удаляя прямоугольники из КД-дерева. При этом каждый раз пересчитывается площадь объединения всех текущих прямоугольников и, складывая эти величины, умноженные на соответствующую разницу <tex>z</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> прямоугольников.
