Algorithm for finding the volume of a convex polytope - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T08:41:42Z http://mathoverflow.net/feeds/question/979 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope Algorithm for finding the volume of a convex polytope Xerxes 2009-10-18T02:01:59Z 2010-02-20T22:28:16Z <p>It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing them into simplices, but gave it up and went with a Monte Carlo estimation scheme instead. Bonus question: How to find the surface area of those same convex bodies?</p> <p>EDIT: To answer David's question: the data set is a Voronoi tessellation of an n-dimensional volume (n usually 4) with a periodic boundary (like a torus). So I have the coordinates of the vertices of the convex bodies as well as the connectivity of all the facets, faces, etc. For the Monte Carlo I mentioned, I did convert everything to half-spaces, so I think that was not very difficult.</p> http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope/989#989 Answer by Reid Barton for Algorithm for finding the volume of a convex polytope Reid Barton 2009-10-18T03:01:33Z 2009-10-18T03:01:33Z <p>I think this problem is hard--the known algorithms are both slow and nontrivial to implement. See <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.7953" rel="nofollow">Exact Volume Computation for Polytopes</a> for a survey. An interesting feature is that there are various algorithms which are well suited for different kinds of polytopes.</p> <p>As a practical answer, <a href="http://www.qhull.org/" rel="nofollow">Qhull</a> can compute volumes and surface areas.</p> http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope/991#991 Answer by David Eppstein for Algorithm for finding the volume of a convex polytope David Eppstein 2009-10-18T03:30:50Z 2009-10-18T03:30:50Z <p>As a follow-up to Barton's response: for hardness results, see I. Bárány &amp; Z. Füredi, Computing the volume is difficult, Discrete and Computational Geometry, 1987. But there are polynomial time approximation schemes for volume of convex bodies independent of dimension, based on random walks within the body: see e.g. M. Dyer, A. Frieze, &amp; R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, J. ACM 1991 and R. Kannan, L. Lovász, &amp; M. Simonovits, Random walks and an O*(n^5) volume algorithm for convex bodies, Random structures and algorithms, 1997.</p> <p>Before getting to these answers, though, it's important to ask: how is your input represented? Is it a convex hull of a set of points, and all you know is the points? Is it an intersection of halfspaces? Is it given to you as an entire face lattice? Also, what range of dimensions do you care about The upper and lower bounds above are quite general but the dimension and input representation may still make a difference to the answer.</p> http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope/7699#7699 Answer by Gabriel Benamy for Algorithm for finding the volume of a convex polytope Gabriel Benamy 2009-12-03T18:45:16Z 2009-12-03T18:52:49Z <p>Here's a fairly straightforward solution for polyhedra (3 dimensions), with running time O(v+ve), where v is the number of vertices and e is the number of edges. I suppose it could be extended to higher dimensions, but it would probably have much worse running time (I fear roughly exponential as in O(v<sup>n</sup>), where n is the number of dimensions).<br><br></p> <p>Let our polyhedron have n vertices, defined by their x,y,z coordinates: v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>n</sub> and let the lowest point be v<sub>1</sub> and the origin (modify the values for the others accordingly), and let it have e edges, defined by the vertices which they connect. Then, since we have coordinates for the vertices (as that is how we defined them), there must be a "ground level" plane p<sub>0</sub> running through the x and z axes (the y-axis being height, and the ground never having an elevation). Then, let v<sub>2</sub> be the point closest to the ground plane (shortest line perpendicular to the plane), and let v<sub>3</sub> be the next closest, etc, through v<sub>n</sub>.<br><br></p> <p>Through each of the points v<sub>2</sub> through v<sub>n</sub>, draw a plane perpendicular to the ground, and let them be numbered p<sub>m</sub>, where m is the subscript of the vertex through which it was drawn. Then, the volume of our polyhedron is equal to the sum of the volumes of the figures between the planes. We should have something resembling this:<br> <img src="http://i158.photobucket.com/albums/t111/JoeMoron2000/planes.jpg" alt="Polyhedron with 6 vertices and 12 edges" /><br><br></p> <p>Let the heights between the segments be h<sub>1</sub> through h<sub>n-1</sub>, where height h<sub>j</sub> is the height between planes p<sub>j</sub> and p<sub>j+1</sub>.<br><br></p> <p>Now, through each plane, we have a polygon (or more, if the figure is concave), whose vertices' coordinates can be calculated easily as follows:<br> Let the edge that runs through the plane p<sub>j</sub> have endpoints v<sub>a</sub> and v<sub>b</sub>. Then, the displacement vector is v<sub>b</sub> - v<sub>a</sub> (assuming the coordinates of v are in vector-form), and the percentage travelled up is $\frac{h_j-h_a}{h_{b-1}-h_a}$. Multiply this by v<sub>b</sub> - v<sub>a</sub> and add to v<sub>a</sub> to calculate the new point of intersection for that edge:<br> Intersection point = $(v_b-v_a)\frac{h_j-h_a}{h_{b-1}-h_a}+v_a$<br> The area of these polygons can be determined using triangles, or a simplification of this very process in just 2 dimensions.<br><br></p> <p><a href="http://planetmath.org/encyclopedia/Bases.html" rel="nofollow">PlanetMath</a> says that the volume of a prismatoid (which is the type of figure contained between sequential planes) is $h\frac{B_1 + B_2 + 4M}{6}$, where the Bs are the areas of the parallel polygons and M is the area of the midway polygon, which is exactly halfway between them (and parallel to them). Since we already know the area of each of the end polygons, and we can easily calculate the vertices of the midway polygon (using the previous paragraph's method), we can calculate the volume of the resulting prismatoids. Adding them up yields the total volume of the polyhedron.<br><br></p> <p>I suppose that the only real issue in this case, then, is, via code, determining which edges run through any particular plane, but if we were to actually look at it, we could tell very easily.<br><br></p> <p>A simpler version of this can be used to figure out the area of any polygon; simply draw lines through the vertices parallel to the x-axis and calculate the area of the resulting trapezoids as (b<sub>1</sub>+b<sub>2</sub>)/2</p> http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope/7754#7754 Answer by David Bar Moshe for Algorithm for finding the volume of a convex polytope David Bar Moshe 2009-12-04T06:05:00Z 2009-12-04T06:05:00Z <p>There is a result by J. Borwein et al on volumes of convex polytopes constructed by intersecting symmetric hyperplanes. These volumes are obtained from multivariate integrals involving the function sin(x)/x. These integrals have very nice closed forms. Here are two references on this work:</p> <p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.8186" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.8186</a></p> <p>and</p> <p><a href="http://algo.inria.fr/seminars/sem01-02/borwein1.pdf" rel="nofollow">http://algo.inria.fr/seminars/sem01-02/borwein1.pdf</a></p> http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope/9135#9135 Answer by Agol for Algorithm for finding the volume of a convex polytope Agol 2009-12-16T23:19:42Z 2009-12-16T23:19:42Z <p>Since you're given so much information about the faces of the polytope, I think that the division into simplices method ought to be straightforward (if tedious) to carry out. The idea is to divide the polytope into <a href="http://en.wikipedia.org/wiki/Orthoscheme" rel="nofollow">orthoschemes</a>, with signed volumes, as described below. This has the advantage that the formula for the volume of an orthoscheme is very simple, and computing the coordinates of the orthoschemes is simple linear algebra. The disadvantage is that there will be one orthoscheme for each <a href="http://en.wikipedia.org/wiki/Flag%5F%28geometry%29" rel="nofollow">flag</a> of the polytope, so the number of them could be quite large. Computing the surface area of the boundary could be done in tandem, since one would just take the area of each orthoschemes intersection with the supporting hyperplanes. I suspect this method won't work for you though, if the polytope is complicated (and maybe this is the approach you already tried). </p> <p>To compute the vertices of the orthoschemes, first choose a point, then take its orthogonal projection to each supporting hyperplane of the polytope. Inductively do this for each facet. The for each flag, take the corresponding points in each face of the flag, and form an orthoscheme. The sign of the volume of the orthoscheme will be determined in each dimension by whether the vertex lies inside or outside the corresponding hyperplane times the sign of the lower dimensional one it is a cone on. Some of the orthoschemes will lie partly outside of the polytope, but the volumes outside will cancel with this sign convention. </p> http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope/10682#10682 Answer by Mathieu Dutour Sikiric for Algorithm for finding the volume of a convex polytope Mathieu Dutour Sikiric 2010-01-04T08:47:33Z 2010-01-04T08:47:33Z <p>As documented above the paper by Bueler, Enge and Fukuda is a good place to start and give many techniques for computing volumes of polytopes. In my experience using lrs to build the triangulation is a very good method. If your polytope has symmetries, then it is possible to use them to reduce the size of the computation. See at <a href="http://www.liga.ens.fr/~dutour/Polyhedral/index.html" rel="nofollow">link text</a> for the relevant programs.</p> http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope/15932#15932 Answer by Jonathan Fine for Algorithm for finding the volume of a convex polytope Jonathan Fine 2010-02-20T21:25:07Z 2010-02-20T21:25:07Z <p>Matthias Beck and Dennis Pixton used almost 17 GigaHertz years to compute the value of the 10-dimensional Birkhoff polytope. Read about it, and find the answer, <a href="http://www.math.binghamton.edu/dennis/Birkhoff/" rel="nofollow">here</a>.</p> <p>If you can get the same result quicker, I'm sure they'd be delighted to know how you did it.</p> http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope/15936#15936 Answer by Justin Melvin for Algorithm for finding the volume of a convex polytope Justin Melvin 2010-02-20T22:28:16Z 2010-02-20T22:28:16Z <p>There is a randomized algorithm with O(n^4) running time based on the simulated annealing using the hit-and-run convex body sampling algorithm along with isotropy approximation by Vempala and Lovasz: <a href="http://www.cc.gatech.edu/~vempala/papers/vol4.ps" rel="nofollow">here</a>. The running time is the number of oracle calls for membership in the convex body and has an implicit polylogarithmic term.</p>