# 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.

-

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. – Rahul Narain Aug 1 '12 at 8:43
– Rahul Narain 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? – Mohsen Aug 3 '12 at 20:16

## 1 Answer

I believe we can reduce the stated problem to your initial question about finding the volume of a convex polytope.

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.

So we're back to, given a finite set, how do we calculate the volume of its convex hull? A little reading around suggests that this is a hard problem. See, e.g. http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope.

-

– Mohsen Aug 3 '12 at 21:17
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
Going in the other direction, the complex you describe subsumes the idea of the chain polytope of a poset, given in terms of the poset's maximal antichains.  Which, is #P to compute given just a description of the poset (it has the same volume as the order polytope which your link talks about).  But this doesn't prove hardness of your question -- a poset may have a number of maximal antichains exponential in its description size. – Managu Aug 7 '12 at 3:00
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9132903218269348, "perplexity_flag": "head"}