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.

  PostScript file (gzipped)   pdf file   free PDF @ACM
other papers about this subject
Last update: August 14, 2017.