BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-733
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: A lower bound to finding convex hulls
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew Chi-Chih
        DATE:: April 1979
       PAGES:: 24
    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.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-733