A Lower Bound to Finding Convex Hulls

Gwen a set S of n distinct points [formula ommited], the convex hull problem is to determine the vertices of the convex hull H(S). All the known algorithms for solving this problem have a worst case runmng time of cn log n or higher and employ only quadratic tests, that is, tests of the form [formula ommited], where f is any polynomial of degree not exceeding 2 It is shown here that any algorithm In the quadratic deciswn-tree model must make cn log n tests for some input.