    Next: How many facets does Up: Convex Polyhedron Previous: What computer models are   Contents

## How do we measure the complexity of a convex hull algorithm?

To answer this question, we assume the unit cost RAM model, where the computational time is essentially the number of elementary arithmetic operations and the storage for any integer number takes a unit space. See Section 2.14.

There are two approaches to evaluate the complexity of a given convex hull algorithm.

Let be an algorithm which computes a minimal inequality description of a full-dimensional convex polytope for a given point set in with . Let denote the number of inequalities in the output .

(One can interprete the discussion here in dual setting: consider as an algorithm to compute all vertices of a convex polytope with inequaities with vertices.)

First of all, most people agree that the efficiency of computing the convex hull should be measured at least by the critical input parameters and . Some people like to see the complexity by fixing to constant, but it is always better to evaluate in terms of as well, and fix it later.

The first measure, often employed by computational geometers, is to bound the worst case running time of an algorithm for any input with points in . For example, if is of , then it means terminates in time for ANY input of points in dimension . Also, when one set to be fixed (constant), such an algorithm is said to have time complexity , since is simply a constant. We may call this worst-case-input measure. For fixed dimension, there is an optimum algorithm [Cha93] for the convex hull in terms of the worst-case-input measure, that runs in time for . It cannot be better because the largest output is of the same order by the upper bound theorem (Theorem 2).

The worst-case-input measure is quite popular, but it might be little misleading. For example, suppose algorithms and are of time complexity and , respectively. Then by this measurement, the algorithm is superior to .

Here is a potentially serious problem with this worst-case-input measure. Above, it is still possible that takes worst-case time for ALL input of points in , and takes time proportional to some polynomial function of . Note that the number of inequalities varies wildly from to , even for fixed (by the upper bound theorem Theorem 2 and (1)). This diversity is just too big to be ignored if . Furthermore, the input data leading to the worst-case output hardly occurs in practice. In fact, for the random spherical polytope, the expected size of is linear in , see Section 2.16. While the worst-case-input optimal algorithm [Cha93] is a remarkable theoretical achievement, we are still very far from knowing the best ways to compute the convex hull for general dimensions.

In order to circumvent this pitfall, one can use a measure using all key variables . Or more generally, one can measure the time complexity in terms of both the size of input and the size of output. We say an algorithm is polynomial if it runs in time bounded by a polynomial in . This polynomiality coincides with the usual polynomiality when the output size is polynomially bounded by the size of input.

Under the nondegeneracy assumption (see 2.12), there is a polynomial algorithm for the convex hull problem. Few of the earlier polynomial algorithms are pivot-based algorithms [CCH53,Dye83] solving the problem in dual form (the vertex enumeration problem) and a wrapping algorithm [CK70]. A more recent algorithm [AF92] based on reverse search technique [AF96] is not only polynomial but compact at the same time. Here, we say an algorithm is compact if its space complexity is polynomial in the input size only.

In the general case, there is no known polynomial algorithm. The paper [ABS97] is an excellet article presenting how various algorithms fail to be polynomial, through ingenious constructions of nasty'' polytopes.    Next: How many facets does Up: Convex Polyhedron Previous: What computer models are   Contents
Komei Fukuda 2004-08-26