Incremental Convex Hull Algorithms Are Not Output Sensitive

Abstract. A polytope is the bounded intersection of a finite set of half-spaces of $$ \Bbb R$$ $$^d$$ . Every polytope can also be represented as the convex hull conv$$ \cal V $$ of its vertices (or extreme points) $$ \cal V $$ . The convex hull problem is to convert from the vertex representation to the half-space representation or (equivalently by geometric duality) vice versa. Given an ordering v1 . . . vn of the input vertices, …