25
правок
Изменения
Нет описания правки
Также, из алгоритма расслоения следует, что из части с <tex>n</tex> точками будет получено по одной части для каждого <tex>i = 1...n</tex>, то есть: <center><tex>f(n, d) = \sum \limits_{i = 1}^{n}f(i, d - 1)</tex>.</center>
1) Покажем, что: <center><tex>{x \choose y} = {x - r \choose y} + \sum \limits_{i = 1}{r} {x - i \choose y - 1}</tex>.</center>
Индукция по <tex>r</tex>. База: <center><tex>{x \choose y} = {x - 1 \choose y} + {x - 1 \choose y - 1}</tex>.</center>
2)
}}
Таким образом, на этот алгоритм получена более низкая оценка времени работы, чем на предыдущий, и это подтверждается на практике [1].
== Сведение к задаче KMP (Klee's Measure Problem) ==
Задача KMP состоит в нахождении объема объединения прямоугольных гиперпараллелепипедов в <tex>d</tex>-мерном пространстве. Как показано в описании алгоритма IEA, исходная задача легко сводится к этой, если каждой точке поставить в соответствие гиперкуб с одной вершиной в центре координат, а противоположной - в этой точке.
Существует несколько алгоритмов решения задачи KMP, самый оптимальный из которых использует идеи сканирующей гиперплоскости, [[Статистики на отрезках. Корневая эвристика|корневой эвристики]] и КД-дерево, и позволяет решать задачу за время <tex>O(n^{d/2}\log n)</tex>. Рассмотрим его.
Для начала изложим идею сканирующей гиперплоскости. Рассмотрим всевозможные значения <tex>d</tex>-ой координаты у точек множества <tex>X</tex>.
Возьмем гиперплоскость, перпендикулярную оси <tex>d</tex>-ой координаты, будем ее двигать по этим значениям от минимального до максимального и рассматривать проекцию всех гиперкубов на эту гиперплоскость. Заметим, что между точками проекция меняться не будет, а в каждой точке будут появляться или исчезать проекции некоторых гиперкубов. Поэтому, если уметь эффективно пересчитывать объем проекции при каждом появлении/исчезновении и прибавлять это значение, умноженное на расстояние между последовательными значениями <tex>d</tex>-ой координаты, то можно легко посчитать суммарный гиперобъем. Как раз для эффективного пересчета используется такая структура, как КД-дерево.
Теперь изложим идею алгоритма на примере трехмерного пространства.
Будем считать, что сканирующая плоскость двигается перепендикулярно оси <tex>OZ</tex>. В каждый момент проекция всех параллелепипедов на эту плоскость предствляет собой множество прямоугольников и необходимо уметь обрабатывать следующие три запроса:
# добавить прямоугольник
# удалить прямоугольник
# посчитать площадь объединения всех прямоугольников
{{Определение
|definition=КД-деревом называется [[Дерево поиска, наивная реализация|сбалансированное двоичное дерево]], где каждой вершине <tex>\alpha</tex> соответствует некоторая область <tex>C_{\alpha}</tex> <tex>d</tex>-мерного пространстве, удовлетворяющая следующим свойствам:
# Корневой вершине <tex>root</tex> соответствует <tex>C_{root}</tex> - все пространство.
# Каждое <tex>C_{\alpha}</tex> является гиперпараллелепипедом (возможно бесконечным в некоторых направлениях).
# Для каждой вершины <tex>\alpha</tex> с детьми <tex>\beta</tex> и <tex>\gamma</tex> верно, что области <tex>C_{\beta}</tex> и <tex>C_{\gamma}</tex> не пересекаются и <tex>C_{\alpha} = C_{\beta} \cup C_{\gamma}</tex>.
}}
Будем хранить прямоугольники в КД-дереве следующим образом:
# Для каждого листа <tex>\alpha</tex> будем хранить все прямоугольники, которые пересекают внутреннюю часть области <tex>C_{\alpha}</tex>.
# Для каждой внутренней вершины <tex>\alpha</tex> будем считать число <tex>Cover_{\alpha}</tex> - количество прямоугольников, которые полностью покрывают область <tex>C_{\alpha}</tex>, но не полностью покрывают область родителя этой вершины <tex>C_{father(\alpha)}</tex>.
Также для каждой вершины будем хранить значение площади пересечения области этой вершины со всеми прямоугольниками <tex>M</tex>, которое определяется следующим образом:
# Для каждого листа <tex>M</tex> равно площади пересечения всех прямоугольников с областью этого листа.
# Для каждой внутренней вершины <tex>\alpha</tex> если <tex>Cover_{\alpha} > 0</tex>, тогда <tex>M</tex> равно площади всех области <tex>C_{\alpha}</tex>, иначе <tex>M</tex> равно сумме этих значений для двух сыновей этой вершины.
Таким образом, значение для корневой вершины <tex>M_{root}</tex> и является искомой площадью объединения всех прямоугольников.
Рассмотрим операцию добавления прямоугольника (box) в КД-дерево.
procedure Insert(box, <tex>\alpha</tex>)
if <tex>\alpha</tex> - лист then
добавить box в эту вершину
пересчитать <tex>M_{\alpha}</tex>
elseif box покрывает область <tex>C_{\alpha}</tex> then
<tex>Cover_{\alpha} = Cover_{\alpha} + 1</tex>
<tex>M_{\alpha} = </tex> объем области <tex>C_{\alpha}</tex>
elseif box пересекает область <tex>C_{\alpha}</tex> then
Insert(box, leftson(<tex>\alpha</tex>))
Insert(box, rightson(<tex>\alpha</tex>))
if <tex>Cover_{\alpha} > 0 </tex> then
<tex>M_{\alpha} = </tex> объем области <tex>C_{\alpha}</tex>
else
<tex>M_{\alpha} = M_{leftson(\alpha)} + M_{rightson(\alpha)}</tex>
Аналогично устроена операция удаления прямоугольника - она выполняет обратные действия.
