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 KEY WORDS AND PHRASES: complexity, convex hull, decision tree, lower bound, quadratic decision-tree model, quadratic test CR CATEGORIES" 5.25, 5.30 1 A point p is a convex combmatlon of the points rl, r2 .... rm If there exist #, _> 0, i = 1, 2, , m, such that ~, #, = 1 and p = ~, #~r,.