4
$\begingroup$

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.

  • 1
    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.2012-08-01
  • 0
    Perhaps more intuitively, it is the set of points dominated (in the sense of [Pareto efficiency](https://en.wikipedia.org/wiki/Pareto_efficiency)) by said convex hull.2012-08-02
  • 0
    @Managu: Thanks for your comment. I don't know how to fix it either. Maybe it's not editable at all?2012-08-03

1 Answers 1