Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Will Sawin Oct 3 '12 at 15:45
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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