10
$\begingroup$

A 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 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; are there other cases?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ slight generalization: those with a polynomial number of vertices $\endgroup$
    – Sasho Nikolov
    Aug 20, 2016 at 14:58
  • 1
    $\begingroup$ @SashoNikolov: Thanks, good point! (A reference for it is repository.cmu.edu/cgi/… -- 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 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). $\endgroup$
    – a3nm
    Aug 23, 2016 at 12:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.