Question

The $H$-representation of a convex polytope $S$, is just a set of linear inequalities corresponding to the intersection of halfspaces: $S = ( x | Ax\leq b )$.

One could also represent a convex polytope as the convex-hull of its vertices, called the $V$-representation: $S = conv(a_1,..., a_m)$.

It is known that sometimes the $H$-representation is much more efficient than the $V$-representation: for example, the unit cube, with $2n$ faces and $2^n$ vertices, whereas in other cases, such as the crosspolytope the $V$-representation of $2n$ vertices is much more efficient than the $H$-representation, which is exponential in $n$.

My question is, is there any general characterization of $V$-polytopes whose $H$-description is exponential, or vice versa?

Answer 1

A generic polytope with $2n$ points in $\mathbb R^n$ has this property. Thus, one can't really characterize such polytopes, unless one can find a way to characterize almost all arrangements of $2n$ points in $\mathbb R^n$

Place $2n$ random points independently identically distributed according to any nontrivial distribution, say a Gaussian or uniformly in the unit cube. There are $\left(\begin{array}{c} 2n \\ n \end{array}\right)$ $n-1$-simplices between sets of $n$ points. Each simplex is a face when all the other points are on one side of it, which happens with probability at least $1/2^{n-1}$, since there are $n$ other points i.i.d. with probability $p$ of being on one side of the face and $1-p$ of being on the other.

Thus, the expected number of faces, and so the size of the $H$ description, is $\frac{1}{2^{n-1}}\left(\begin{array}{c} 2n \\ n \end{array}\right)\approx \frac{2^n}{\sqrt{n\pi}}$. So all these polytopes have linear $V$-description but exponential $H$-description.

To go the other way, just take the dual polytope.