Report Number: CS-TR-79-733
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.