<p>A <em><a href="https://en.wikipedia.org/wiki/Convex_polytope" rel="nofollow">convex polytope</a></em> is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The <em>volume computation problem</em> for convex polytopes asks, given such a polytope $P$, what is its volume $V(P)$, expressed as a rational number. The size of the input $||P||$ is accounted by writing out the inequalities, with rational numbers written as a pair of numerator and denominator (as binary numbers), and the size of the output $||V(P)||$ is defined in the same way.</p>

<p>It was shown by Lawrence in <a href="http://www.ams.org/journals/mcom/1991-57-195/S0025-5718-1991-1079024-2/" rel="nofollow">this paper</a> that there are convex polytopes $P$ for which $||V(P)||$ is exponential in $||P||$, implying, e.g., that the volume computation problem is not in FP$^{\#\mathrm{P}}$. My question is: <strong>are there known classes of convex polytopes for which $||V(P)||$ is polynomial in $P$?</strong> I know that this is the case, e.g., of <a href="https://en.wikipedia.org/wiki/Simplex#Volume" rel="nofollow">simplices</a>; are there other cases?</p>

CC BY-SA 3.0
2016-08-20T14:58:59.433Z
slight generalization: those with a polynomial number of vertices
Sasho Nikolov
CC BY-SA 3.0
2016-08-23T12:30:17.053Z
@SashoNikolov: Thanks, good point! (A reference for it is http://repository.cmu.edu/cgi/viewcontent.cgi?article=1441&context=math -- comments at the end of Section 3). But it does not cover all cases of polynomial bit-length. For instance, order polytopes (the polytopes contained in $[0, 1]^n$ defined by inequalities of the form $x_i \leq x_j$) have polynomial bit length (because they can be partitioned in total orders, see https://www.math.ucdavis.edu/~lrademac/centroid.pdf lemma 4) but they may not have polynomially many vertices (for the empty order, the cube $[0, 1]^n$ has $2^n$ vertices).
Antoine Amarilli 'a3nm'
<reference-request><computational-geometry><convex-geometry><polytope>
Which convex polytopes have volumes of polynomial bit-length?
Antoine Amarilli 'a3nm'
# Which convex polytopes have volumes of polynomial bit-length?

(Asked by: username_0 on 2016-08-18)

A *[convex polytope](https://en.wikipedia.org/wiki/Convex_polytope)* is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The *volume computation problem* for convex polytopes asks, given such a polytope $P$, what is its volume $V(P)$, expressed as a rational number. The size of the input $||P||$ is accounted by writing out the inequalities, with rational numbers written as a pair of numerator and denominator (as binary numbers), and the size of the output $||V(P)||$ is defined in the same way.

It was shown by Lawrence in [this paper](http://www.ams.org/journals/mcom/1991-57-195/S0025-5718-1991-1079024-2/) that there are convex polytopes $P$ for which $||V(P)||$ is exponential in $||P||$, implying, e.g., that the volume computation problem is not in FP$^{\#\mathrm{P}}$. My question is: **are there known classes of convex polytopes for which $||V(P)||$ is polynomial in $P$?** I know that this is the case, e.g., of [simplices](https://en.wikipedia.org/wiki/Simplex#Volume); are there other cases?

**Tags:** reference-request, computational-geometry, convex-geometry, polytope

> **Comments:**
> **username_1**: slight generalization: those with a polynomial number of vertices  
> **username_0**: @SashoNikolov: Thanks, good point! (A reference for it is http://repository.cmu.edu/cgi/viewcontent.cgi?article=1441&context=math -- comments at the end of Section 3). But it does not cover all cases of polynomial bit-length. For instance, order polytopes (the polytopes contained in $[0, 1]^n$ defined by inequalities of the form $x_i \leq x_j$) have polynomial bit length (because they can be partitioned in total orders, see https://www.math.ucdavis.edu/~lrademac/centroid.pdf lemma 4) but they may not have polynomially many vertices (for the empty order, the cube $[0, 1]^n$ has $2^n$ vertices).  

---

## 0 answers

