## Günter Rote:

# Degenerate convex hulls in high dimensions without extra storage (extended
abstract)

In: *Proceedings of the Eighth Annual Symposium on Computational
Geometry, Berlin, June 10–12, 1992.* Association for
Computing Machinery, 1992; pp. 26–32.
doi:10.1145/142675.142685
### Abstract

We present an algorithm for enumerating the faces of the convex hull
of a given set *P* of *n* points in *d* dimensions.
The main features of the algorithm are that it uses little extra storage and
that it addresses degeneracy explicitly.
It is based on an idea that was recently introduced by Avis and Fukuda (1991)
for their convex hull algorithm: The idea is to take a pivoting rule from
linear programming and to “invert” the path that it takes to the optimal
solution in all possible ways, thereby visiting all feasible bases in a
depth-first search manner.

Theoretical considerations and computational tests have established that the
method takes a long time for degenerate point sets.
The reason is that, in the case of degenerate polytopes, the number of
feasible bases may exceed the number of facets by far.

Therefore we propose a variation of the method that takes degeneracies into
account explicitly: Instead of visiting all feasible bases, the algorithm
visits all *facets*.
The manner of visiting facets is analogous to the convex hull algorithm of
Chand and Kapur (1970) as it is described and analyzed in Swart (1985).

We also propose a hybrid algorithm that saves time in nondegenerate cases,
thus becoming even more competitive with Avis and Fukuda's algorithm.

Last update: August 14, 2017.