A lower bound to finding convex hulls

[摘要] 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.

[学科分类] 计算机科学（综合）