Алгоритмы точного вычисления гиперобъема

Эта статья находится в разработке!

Постановка задачи

[math]x = (x_1, x_2, ..., x_d; x_i \ge 0) \in R^d[/math] - точка в [math]d[/math]-мерном пространстве.

Точка [math]x[/math] доминирует точку [math]y[/math] ([math]x \succ y[/math]), если [math]\forall i : x_i \ge y_i, \exists j : x_j \gt y_j[/math].

[math]X = (x^1, x^2, ..., x^n) \subset R^d[/math] - множество из [math]n[/math] точек в [math]d[/math]-мерном пространстве таких, что [math]\nexists i \neq j : x_i \succ x_j[/math] - никакая точка не доминируется другой точкой из этого множества.

[math]S(X) = \mu (\bigcup \limits_{x \in X} \{y | y \succ x\}) [/math] - гиперобъем множества [math]X[/math].

В частности, если [math]X = \{x\}[/math], то [math]S(X) = \prod \limits_{i=1}^{d} x_i[/math].

Задача: найти точное значение гиперобъема [math]S(X)[/math] множества из [math]n[/math] точек [math]d[/math]-мерного пространоства.

Алгоритм включения-исключения (Inclusion-Exclusion Algorithm, IEA)

Самый простой алгоритм нахождения гиперобъема базируется на идее комбинаторной формулы включения-искючения. Все множество [math]X[/math] представляется в виде объединения [math]n[/math] гиперкубов ([math]X^i[/math]), соответствующих отдельным точкам [math]x^i[/math].

После этого объем всего множества вычисляется по формуле: [math] S(X) = \sum \limits_{I \in 2^n} (-1)^{|I|+1} S(\bigcap \limits_{ j \in I} X^j) [/math]

Объем пересечения гиперкубов легко считается как произведение по каждой координате минимального значения этой координаты среди всех точек, которым соответствуют гиперкубы.

Таким образом, в этом алгоритме перебираются все подмножества точек множества [math]X[/math], для каждого множества находится гиперобъем пересечения соответствующих гиперкубов и он прибавляется с соответствующим знаком к ответу. Время работы этого алгоритма составляет [math]O(n 2^n)[/math].