Computing the volume of a simplex-like object with constraints

Question

For any $n \geq 2$, let $$D_n [r , (a_1, b_1 ) , \ldots , (a_n, b_n) ] = \{ (x_1 , \ldots , x_n ) \in \mathbb R^n \mid \sum_i x_i = r \mbox{ and } b_i \geq x_i \geq a_i \, \forall i \},$$ where $r \geq b_i \geq a_i \geq 0$ for all $i$, and all are real numbers.

Question: What is the 'volume' of $D_n [r , (a_1, b_1 ) , \ldots , (a_n, b_n) ]$?

So for example for $n=2$, this set is either empty or it is some short line, and the purpose would be to calculate the length of that line (in terms of the parameters $r, a_i, b_i$). This is easy, I've done that already. Also the case $n=3$ would in principle still be doable to do by hand: it would be either zero (in case the set is empty) or part of a plane in $\mathbb R^3$, the area of which we desire to compute.

Now to come up with a formula for the case $n=3$ (and higher) in a smarter way, my idea was to reason inductively from the case $n=2$, so basically reducing the three dimensional case to the two dimensional one, etc. I obviously tried to use integrals.

The problem I run into, is that in order to compute the volume we want with integrals, we have to view this set as (a subset of) an $n-1$-dimensional space. (Indeed, the integral of the constant function $1$ over the region $D_n [r , (a_1, b_1 ) , \ldots , (a_n, b_n) ]$ seen as part of $\mathbb R^n$ (rather than $\mathbb R^{n-1}$), is equal to $0$. That's not what we want.) But to do that, it seems to me that we would need a concrete isometric embedding of $D_n [r , (a_1, b_1 ) , \ldots , (a_n, b_n) ]$ into $\mathbb R^{n-1}$, and I can't really find a nice one.

Do you have an idea about how to approach this problem best?

(This question was previously posted on Math.StackExchange, see https://math.stackexchange.com/questions/3135606/computing-hyper-area-of-a-contrained-simplex.)

Answer 1

Computing volumes of polytopes in general is NP-hard. However, your polytope is special - it is a slice of a hypercube by a hyperplane, and this is tractable, see Theorem 1 in:

Marichal, Jean-Luc; Mossinghoff, Michael J., Slices, slabs, and sections of the unit hypercube, Online J. Anal. Comb. 3, Article 1, 11 p. (2008). ZBL1189.52011.

Answer 2

The $(n-1)$-volume of your polytope (in $\mathbb R^n$) equals the $(n-1)$-volume of the polytope \begin{multline} P:=\{(x_1,\dots,x_{n-1})\in\mathbb R^{n-1}\colon \\ a_i\le x_i\le b_i\ \forall i=1,\dots,n-1,\\ a_n\le r-\sum_1^{n-1}x_i\le b_n\} \end{multline} (in $\mathbb R^{n-1}$) divided by $1/\sqrt n$, which latter is the cosine of the angle between the unit vectors $(1/\sqrt n,\dots,1/\sqrt n)$ and $(0,\dots,0,1)$ in $\mathbb R^n$ -- because $P$ is the image of your polytope under the orthogonal projection of $\mathbb R^n$ onto $\mathbb R^{n-1}$ given by $(x_1,\dots,x_n)\mapsto(x_1,\dots,x_{n-1})$. The unit vectors $(1/\sqrt n,\dots,1/\sqrt n)$ and $(0,\dots,0,1)$ are normal vectors to, respectively, the hyperplane containing your polytope and the hyperplane $\{(x_1,\dots,x_n)\in\mathbb R^n\colon x_n=0\}$; the latter hyperplane is identified with $\mathbb R^{n-1}$.

A formula for the volume of a polytope was given by Lawrence.

Answer 3

We may assume without loss of generality that $a_i=0$. If $r$ and each $b_i$ are positive integers, then consider $$ f(x) = \frac{\left( 1-x^{tb_1+1}\right)\cdots \left( 1-x^{tb_n+1}\right)}{(1-x)^n}. $$ The coefficient of $x^{tr}$ is a polynomial function of $t$, and the volume $V$ will be its leading coefficient. If I didn't make a computational error, then $$ V=\frac{1}{(n-1)!}\sum_{\substack{S\subseteq \{1,\dots,n\}\\ \sum_{i\in S}b_i<r}} (-1)^{|S|} \left(r-\sum_{i\in S}b_i\right)^{n-1}. $$ If this isn't correct, then something close to it will be.