Incremental convex hull algorithms are not output sensitive

A polytope is the bounded intersection of a finite set of half-spaces of ℝd. Every polytope can also be represented as the convex hull conv ν of its vertices (extreme points) ν. 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 v1 ... vn of the input vertices, after some initialization an incremental convex hull algorithm …