1
$\begingroup$

This is rather specific but I need to compute the volume under the intersection of rescaled simplexes, that is, the volume of the space:

$\left\{x \in \mathbb{R}^n|\sum_i c_{ki} |x_i| \leq1\; k = 1 \dots m\right\}$

with $c_{ki} > 0$.

If there is only one simplex, $m=1$ the answer is simply:

$\frac{2^n}{(n+1)!} \prod_i c_{1i}$

However, in the case I am considering there usually is a large number of rescaled simplicies, $m > n$.

That of course also means that its entirely possible that some of the constraints are redundant. I have found various papers, (e.g. [1]) discussing algorithms that can efficiently compute intersections of convex polytopes, numerically this should thus be efficient.

As the problem is only slightly more specific than the general case, I suspect that I can't do a better, and a closed formula for this volume does not exist. As this is fairly far outside my realm of expertise I wanted to ask here if this intuition is correct or whether there is an angle from which to attack this issue.

[1] Bringmann and Friedrich, 2010 http://people.mpi-inf.mpg.de/~tfried/paper/CGTA1.pdf

Edit:

I just realized one case that seems to be treatable is $n=m$ and $c_{ik}$ invertible. Then there is exactly one $x^\text{corner}$ with $\sum_i c_{ki} x_i = 1$. Thus if $x_i > 0$, I think the space in each quadrant is the convex hull of $\min_k c_{ki}$, $x^\text{corner}_i = \sum_k c^{-1}_{ik}$ and the origin. This means the space is composed of two $n+1$ simplexes, one with the origin, and the other with $x^\text{corner}$ which solves the problem.

I guess the correct way to phrase the question thus is: How does the additional structure I have help me chop the resulting space up into simplexes.

$\endgroup$
2
  • $\begingroup$ looks like a particular case of the volume of a polytope. $\endgroup$ Mar 31, 2015 at 11:42
  • $\begingroup$ That's a good point. However I need this for n=k=100 and more, thus the general purpose algorithms seem not particularly useful here. After writing this up I realized there is one special case I can handle, I'll add an edit. $\endgroup$ Mar 31, 2015 at 12:04

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.