the upper-bound theorem

Suppose you fix the number of vertices of a polytope but let it be as intricate as it can in n-dimensional space — what is the most faces it can possibly have? The upper-bound theorem answers exactly this: among all n-dimensional polytopes with a given number of vertices, the cyclic polytope is the champion, having the maximum possible number of faces of every dimension. It pins down the worst-case combinatorial complexity, which is why it is the foundational estimate in computational geometry.

Precisely, let P be a simplicial n-polytope with N vertices (the simplicial assumption is no loss for the maximum, since perturbing a polytope only increases face counts). Then for every k, the number f_k of k-faces of P is at most f_k of the cyclic polytope C(N, n) — the convex hull of N points on the moment curve t -> (t, t^2, ..., t^n). The cyclic polytope is neighborly: every subset of up to floor(n/2) of its vertices forms a face, which is the most any n-polytope can manage, and this neighborliness is what makes it maximal. McMullen proved the theorem in 1970 using the h-vector and the Dehn-Sommerville relations; the key inequality is that the h-vector of any simplicial polytope is dominated entrywise by that of the cyclic polytope.

The practical punchline is a sharp growth rate: an n-polytope with N vertices can have on the order of N^{floor(n/2)} facets, and no more. This is why convex-hull and Voronoi-diagram algorithms in dimension n have worst-case output size (and hence running time) growing like N^{floor(n/2)} — the upper-bound theorem is the reason high-dimensional convex hulls explode. An honest caveat: the bound is tight (cyclic polytopes achieve it) but pessimistic for typical inputs; random or generic point sets usually have far fewer faces, so the theorem describes the worst case, not the average. Also note it bounds faces from ABOVE; the matching lower-bound theorem, with the stacked polytope as extremal, is a separate result.