4
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Obviously, due to the fact that the dual polytope operation switches the $V$-representation and the $H$-representation, a characterization one way would imply a characterization the other way. $\endgroup$
    – Will Sawin
    Oct 3, 2012 at 15:45

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.