Institution: Stanford University, Department of Computer Science

Title: A lower bound to finding convex hulls

Author: Yao, Andrew Chi-Chih

Date: April 1979

Abstract: Given a set S of n distinct points {($x_i$,$y_i$) | 0 $\leq$ i < 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 running time of cn log n or higher, and employ only quadratic tests, i.e., tests of the form f($x_0$, $y_0$, $x_1$, $y_1$,...,$x_{n-1}$, $y_{n-1}$): 0 with f being any polynomial of degree not exceeding 2. In this paper, we show that any algorithm in the quadratic decision-tree model must make cn log n tests for some input.

http://i.stanford.edu/pub/cstr/reports/cs/tr/79/733/CS-TR-79-733.pdf