This paper presents an algorithm and its probabilistic analysis for constructing the convex hull of m given points in ℝn, the n-dimensional Euclidean space. The algorithm under consideration combines the Gift-Wrapping concept with the so-called Throw-Away Principle (introduced by Akl and Toussaint and later by Devroye) for nonextremal points. The latter principle had been used for a convex-hull-construction algorithm in ℝ2 and for its probabilistic analysis in a recent paper by Borgwardt et al. There, the considerations remained much simpler, because in ℝ2 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 an n × 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 our m random points are distributed identically, independently, and symmetrically under rotations in ℝn. 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: (i) a parametrization of the expected effort can be given; (ii) the dependence on n – the dimension of the space – can be evaluated; (iii) the additional work of preprocessing for detecting the vertices can be avoided without losing its advantages.
