A Lower Bound to Finding Convex Hulls

Abstract

Gwen a set S of n distinct points {(x,, y,)(O _< l < n }, 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 formf(x0, y0, xl, yl, . , xn-~, yn-0:0, 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