Incremental convex hull algorithms are not output sensitive

A polytope is the bounded intersection of a finite set of half-spaces of R- d. Every polytope can also be represented as the convex hull conv V of its vertices (or extreme points) V. The convex hull problem is to convert from the vertex representation to the halfspace representation or (equivalently by geometric duality) vice versa. Given an ordering v(l) ... v(n) of the in put vertices, after some initialization an incremental convex hull algorith m constructs half-space descriptions Hn-k ... H-n where H-i is the half-spa ce description of conv {v(l) ... v(i)}. Let m(i) denote \H-i\, and let m de note m(n). Let phi(d) denote d/[root d] - 1; in this paper we give families of polytopes for which m(n-1) is an element of Omega (m(phi(d))) for any o rdering of the input. We also give a family of 0/1-polytopes with a similar blowup in intermediate size. Since m(n-1) is not bounded by any polynomial in m, n, and d, incremental convex hull algorithms cannot in any reasonabl e sense be considered output sensitive. It turns out that the same families of polytopes are also hard for the other main types of convex hull algorit hms known.