Primal-dual methods for vertex and facet enumeration (preliminary version)
David Bremner, Komei Fukuda, Ambros Marzetta · 1997
Every convex polytope can be representedas the intersectionof a finiteset of halfspaccs and as theconvex hull of its vertices.Transforming from the halfspace (respectively vertex) to the vertex (respectively halfspace) representationis called vertex enumeration (respectivelyjhcet enumeration).An open questionis whetherthere is analgorithmfor thesetwoproblems(equivalentby geometric du- ality) thatis polynomial in theinputsize and theoutputsize.In this papr, we extend theknown polynomially solvable classes of polytopes by looking at thedual problems.The dud problem of a vertex (facet, respectively) enumerationproblem is the facet (vertex)enumerationproblem for the same polytope where theinputand output are simply interchanged.For a particularclass of polytopes and a fixed algorithm, one transformationmay be much easier than its dual.In this paper, we propose a new class of algorithmsthattake advantageof this phenomenon.Ltmely speaking,prinra14ual algorithmsuse a solution to the easy direction as an oracle to help solve the seemingly harddkection.