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.