Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

This paper presents an algorithm and its probabilistic analysis for constructing the convex hull ofm given points in ?ⁿ then-dimensional Euclidean space. The algorithm under consideration combines the Gift-Wrapping concept with the so-called Throw-Away Principle (introduced by Akl and Toussaint [1] and later by Devroye [10]) for nonextremal points. The latter principle had been used for a convex-hull-construction algorithm in R² and for its probabilistic analysis in a recent paper by Borgwardtet al. [5]. There, the considerations remained much simpler, because in ?² the construction of the convex hull essentially requires recognition of the extremal points and of their order only. In this paper the Simplex method is used to organize a walk over the surface of the convex hull. During this walk all facets are discovered. Under the condition of general position this information is sufficient, because the whole face lattice can simply be deduced when the set of facets is available. Exploiting the advantages of the revised Simplex method reduces the update effort to ann ×n matrix and the number of calculated quotients for the pivot search to the points which are not thrown away. For this algorithm a probabilistic analysis can be carried out. We assume that ourm random points are distributed identically, independently, and symmetrically under rotations in Rⁿ. Then the calculation of the expected effort becomes possible for a whole parametrical class of distributions over the unit ball. The results mean a progress in three directions:

a parametrization of the expected effort can be given;

the dependency onn— the dimension of the space—can be evaluated;

the additional work of preprocessing for detecting the vertices can be avoided without losing its advantages.