<p>You can try and use qhull <a href="http://www.qhull.org/">http://www.qhull.org/</a> - it can compute the volume of the convex hull of the vertices. However, a priori I do not see any reason for it to perform reasonably for your range of numbers. If qhull does not work, you can try CGAL/GALIA. In the worst case, you can try and impelement one of the random walk algorithms you mentioned - they should not be too hard to implement in this case, but the constants involved might be very large...</p>

CC BY-SA 3.0
2012-01-05T03:00:34.523Z
Thank you, Sariel! Qhull worked for me for d = 10, n = 32, but seems to be stuck forever for d = 15, n = 64. Given the algorithms that it implements, it looks like it is more oriented on low-dimensional spaces. Is there any chance that there might be an analysis of the asymptotic running time for convex hull algorithms, depending on these two parameters?
Grigory Yaroslavtsev
CC BY-SA 3.0
2012-01-05T03:06:44.513Z
Actually, the website says: "For convex hulls and halfspace intersections, Qhull may be used for 2-d upto 8-d." So it's not surprising that it got stuck for 15-d.
Grigory Yaroslavtsev
CC BY-SA 3.0
2012-01-05T03:15:13.453Z
Currently, Fukuda's cdd (http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html) seems most promising, I will try to play with it.
Grigory Yaroslavtsev
CC BY-SA 3.0
2012-01-06T02:22:12.057Z
Well. IT is known that a polytope with $n$ vertices in $d$ dimensions has in the worst case $n^{\floor{d/2}}$ facets. Putting $n$ points on the moment curve in $d$ dimensions provide you with such a polytope. It seems to me unlikely that volume computation can be done faster than the nubmer of facets. So you really have to implement the random walk papers if you want better results....
Sariel Har-Peled
CC BY-SA 3.0
2012-01-03T02:18:01.150Z
2012-01-03T02:18:01.150Z
Sariel Har-Peled
<p>I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-dimensional space with parameters bounded roughly as follows: $d \le 50$  and $n \le 1000$. Note, that there is no guarantee on the number of faces.</p>

<p><a href="http://www.cs.uiuc.edu/~jeffe/compgeom/code.html#topes">Jeff Erickson's page</a> has a link to a program <a href="http://www.mathpool.uni-augsburg.de/~enge/Volumen.html">Vinci-1.0.5</a>, which has a hard limit of 255 faces. This is a limitation of the implementation, the algorithm itself can probably handle more faces in reasonable time.</p>

<p>I couldn't find any implementations of the Markov chains based method for estimation, although I guess they will be even less efficient.</p>

<p>Is there any software, that can handle the range of parameters described above or some moderate relaxation of it? I would be very grateful for any other references as well.</p>

<cg.comp-geom><software><convex-geometry><high-dimensional-geometry>
Computing volume of high-dimensional convex polyhedra
Grigory Yaroslavtsev
# Computing volume of high-dimensional convex polyhedra

(Asked by: username_0 on 2012-01-02)

I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-dimensional space with parameters bounded roughly as follows: $d \le 50$ and $n \le 1000$. Note, that there is no guarantee on the number of faces.

[Jeff Erickson's page](http://www.cs.uiuc.edu/~jeffe/compgeom/code.html#topes) has a link to a program [Vinci-1.0.5](http://www.mathpool.uni-augsburg.de/~enge/Volumen.html), which has a hard limit of 255 faces. This is a limitation of the implementation, the algorithm itself can probably handle more faces in reasonable time.

I couldn't find any implementations of the Markov chains based method for estimation, although I guess they will be even less efficient.

Is there any software, that can handle the range of parameters described above or some moderate relaxation of it? I would be very grateful for any other references as well.

**Tags:** cg.comp-geom, software, convex-geometry, high-dimensional-geometry


---

## 1 answers

### Answer by username_1 on 2012-01-03. Score: 7

You can try and use qhull <http://www.qhull.org/> - it can compute the volume of the convex hull of the vertices. However, a priori I do not see any reason for it to perform reasonably for your range of numbers. If qhull does not work, you can try CGAL/GALIA. In the worst case, you can try and impelement one of the random walk algorithms you mentioned - they should not be too hard to implement in this case, but the constants involved might be very large...

> **Comments:**
> **username_0**: Thank you, Sariel! Qhull worked for me for d = 10, n = 32, but seems to be stuck forever for d = 15, n = 64. Given the algorithms that it implements, it looks like it is more oriented on low-dimensional spaces. Is there any chance that there might be an analysis of the asymptotic running time for convex hull algorithms, depending on these two parameters?  
> **username_0**: Actually, the website says: "For convex hulls and halfspace intersections, Qhull may be used for 2-d upto 8-d." So it's not surprising that it got stuck for 15-d.  
> **username_0**: Currently, Fukuda's cdd (http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html) seems most promising, I will try to play with it.  
> **username_1**: Well. IT is known that a polytope with $n$ vertices in $d$ dimensions has in the worst case $n^{\floor{d/2}}$ facets. Putting $n$ points on the moment curve in $d$ dimensions provide you with such a polytope. It seems to me unlikely that volume computation can be done faster than the nubmer of facets. So you really have to implement the random walk papers if you want better results....  

---

