Dueling cubes

Abstract

This paper promotes the idea of understanding a (convex) polytope as the convex hull of 'just the right subset of polytopes'. This idea may be especially useful when a minimal sized external representation of a polytope appears to be non-polynomial but where the polytope can also be shown to be a convex combination of a polynomial sized set of polytopes, each having a polynomial sized external representation. As an example, polytope ℂ is defined as the convex hull of the set of extrema of both a cube and its dual. ℂ is then shown to be an exponential faceted and exponential extreme point polytope. A minimal sized external representation of ℂ, in the space defined by the cube and its dual, is therefore exponential. An external representation of ℂ however, can also be constructed as the convex combination of the linear sized external representation of a cube and the linear sized external representation of its dual showing that ℂ in fact has a linear sized external representation.