H-representation versus V-representation of polytopes 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 = \mathrm{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?
 A: 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.
