A Lower Bound to Finding Convex Hulls
Andrew Chi-Chih Yao · Journal of the ACM · 1981
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.30We use O(g(n)) to denote any functlonf(n) with the property that clg(n) _< f(n) _< c2g(n) for some positive constants ci, c2 and all sufficiently large n.