9
$\begingroup$

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 has a link to a program Vinci-1.0.5, 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.

|cite|improve this question
$\endgroup$
7
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Grigory Yaroslavtsev Jan 5 '12 at 3:00
  • $\begingroup$ 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. $\endgroup$ – Grigory Yaroslavtsev Jan 5 '12 at 3:06
  • $\begingroup$ Currently, Fukuda's cdd (cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html) seems most promising, I will try to play with it. $\endgroup$ – Grigory Yaroslavtsev Jan 5 '12 at 3:15
  • $\begingroup$ 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.... $\endgroup$ – Sariel Har-Peled Jan 6 '12 at 2:22

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.