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?

$\endgroup$
  • 1
    $\begingroup$ slight generalization: those with a polynomial number of vertices $\endgroup$ – Sasho Nikolov Aug 20 '16 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 '16 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.