6
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.