# Computing the volume of a set efficiently

Given a set of vectors $\mathbf v_i$ for $i=1,\dots,k$, $\mathbf v_i \in \{0,1\}^n$, is that possible to efficiently find the volume of the set,

$$\left\{\mathbf x \in [0,1]^n:\mathbf x \le \sum_{i=1}^k \alpha_i\mathbf v_i\ \text{for some \alpha_i}\right\},$$ such that $\sum_i \alpha_i=1$ and $\alpha_i \ge 0$. The comparison $\mathbf x \le \sum_{i=1}^k \alpha_i\mathbf v_i$ is taken componentwise.

Note: the above question arose from another question asked by me previously.

-
To all concerned: This is the union of the boxes $[0,x_1]\times[0,x_2]\times\cdots\times[0,x_n]$ for all $\mathbf x=(x_1,x_2,\ldots,x_n)$ in the convex hull of the input vectors. –  Rahul Aug 1 '12 at 8:43
Perhaps more intuitively, it is the set of points dominated (in the sense of Pareto efficiency) by said convex hull. –  Rahul Aug 2 '12 at 0:44
@Managu: Thanks for your comment. I don't know how to fix it either. Maybe it's not editable at all? –  Helium Aug 3 '12 at 20:16

First, the set you describe, call it $A$ is convex. In fact, we can specify a generating set for it. For each 0-1 vector $\mathbf b\in\{0,1\}^n$, let $p_\mathbf b(\mathbf x)=(x_1\cdot b_1, x_2\cdot b_2,\ldots,x_n\cdot b_n)$. That is, $p$ takes a vector $x$ and, in each place, replaces the coordinate with $0$ or leaves the coordinate alone, according to whether $b$ is $0$ or $1$. Then $A$ is the convex hull of $P=\left\{p_b(\mathbf{v}_i) : 0<i\leq k, \mathbf{b}\in \{0,1\}^n\right\}$. Note that this set contains at most $k\cdot 2^n$ elements.
Everything I've looked at suggests that really bad behavior tends to happen as the dimension goes up moreso than as the number of points goes up. And a lot of the funky examples are given in the halfspace representation of a polytope, instead of the vertex representation as I'm discussing here. If your dimension is fixed, I suspect the volume can be computed in time poly(|V|). –  Managu Aug 7 '12 at 2:22