Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a set of inequalities, I am looking for a way to compute its volume. More specifically, I would like to compute the ratio of its volume with the volume if some more inequalities were added. I have seen this question, I think however that half-plane intersections can be general convex polytopes (not just simplexes, am I wrong?).

I do not think I can expect a formula, an efficient algorithm would do (even an efficient one would be nice). Numerical method suggestions are also welcome.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

If you are ok with approximate result, just use Monte Carlo method and if you want exact solution (like a rational number) then I think you will need to enumerate all the vertices (each vertex is given as a solution of set of some $n$ independent linear equations taken from those inequalities) and split into $n$-cells (like triangulation of some polygon) and sum the volume of those $n$-cells.

I think there might be some more efficient method by splitting this polytope by hyperplanes parallel to $\{x = 0\}$ or $\{y = 0\}$ or something similar, but this looks like a more complicated approach.

Finally there is yet another approach that splits your polytope by $|V|$ hyperplanes parallel to $\{x = 0\}$ passing through each vertex, and then volume of such slice can be computed by manipulating the $(n-1)$-volumes of the two sides, which can be computed by recursive call in a smaller dimension. This is not an efficient algorithm, but it will give a precise result and I think it won't be a nightmare to code (after all, I guess, the number of inequalities and the dimension of the space may vary, so it might be a good approach to code it independently of those two).

Edit: To answer your comment: Well, I don't have much time right now, but I will sketch a possible solution (there may be a better one, but I don't know, this is just a simple approach that came to me at the time of writing the post). Let $A \subset \mathbb{R}^n$ be your $n$-dimensional polytope, and $\mu_k$ be the $k$-dimentional Lebesgue measure (i.e. $k$-volume). Consider a function $$f(x) = \mu_{n-1}(\{p\in A \mid p_0 = x\}).$$ This is a piecewise $(n-1)$-th degree polynomial, e.g. if $n=2$ then you can split your polygon into trapezoids, and $f$ would be piecewise linear, if $n=3$ then you can split your polygon into prismatoids and $f$ would be piecewise quadratic. To obtain the volume of $A$ just integrate $f$ and you are done (this is a polynomial, so it is easy to get the exact result). And how to get $f$? Pieces are exactly created by the vertices, so in $n=3$ case you will need both sides (which you are computing anyway) and something in-between (actually you need $n$ points total for each piece, that means $n-2$ additional points). However, each of these can be solved using a recursive call to this algorithm for smaller dimension, and after that you have $n=3$ data points that uniquely describe a polynomial of $(n-1=2)$-nd degree.

Edit 2: After some reconsideration instead of integration consider just using some quadrature, the result still will be precise (if the order is high enough) and this should skip you the polynomial-fitting part.

However, I think that the approach using $n$-cells may be better. It is simple to calculate the volume of $n$-cell, so the algorithm could be as follows: take random $n$ points and split the polytope by resulting hyperplane into two parts and compute the results recursively. When the number of points is small, just do not take random points (choose them, so the resulting split is good), and finally for each part you will end up with $n+1$ points from which you can easily compute the volume.

Hope this helps!

share|improve this answer
    
I am interested in the last suggestion, I just don't fully understand it.. Can you maybe explain it in 3D as an example, or can you link to a longer description? –  aelguindy Apr 23 '12 at 13:09
    
@aelguindy The comment was too short. I hope this helps ;-) –  dtldarek Apr 23 '12 at 19:23
    
Now I understand better. I still find it very complicated to implement, even though the solution is exponential (the number of points is exponential in number of inequalities). I think I will go with the Monte Carlo solution. Btw, I stumbled upon this. –  aelguindy Apr 24 '12 at 9:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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