25
правок
Изменения
м
Нет описания правки
Таким образом, в этом алгоритме перебираются все подмножества точек множества <tex>X</tex>, для каждого множества находится гиперобъем пересечения соответствующих гиперкубов и он прибавляется с соответствующим знаком к ответу.
Время работы этого алгоритма составляет <tex>O(n 2^n)</tex>.
== Алгоритм LebMeasure ==
Алгоритм LebMeasure обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировшуюся до этого точкой <tex>x</tex>.
Например, если изначально было четыре точки в трехмерном пространстве <center><tex>(6, 7, 4), (9, 5, 5), (1, 9, 3), (4, 1, 9)</tex>, </center> то точка <tex>(6, 7, 4)</tex> эксклюзивно доминирует куб с одним концов в <tex>(6, 7, 4)</tex>, а другим - в <tex>(4, 5, 3)</tex>. После добавления объема этого куба в ответу, точка <tex>(6, 7, 4)</tex> порождает три точки: <center><tex>(4, 7, 4), (6, 5, 3), (6, 7, 3)</tex>.</center>При этом, точка <tex>(6, 5, 4)</tex> доминируется точкой <tex>(9, 5, 5)</tex> и сразу удаляется из множества <tex>X</tex>.
Обработка точек продолжается, пока все точки не будут обработаны. Таким образом, время работы алгоритмы напрямую зависит от количества порожденных точек. Легко заметить, что таких точек не более, чем <tex>n^d</tex>, поскольку каждая координата каждой порожденной точки равна соответствующей координате некоторой точки исходного множества <tex>X</tex>.
