  In general dimension, there is no known total polynomial algorithm for either
convex hull or vertex enumeration, i.e. an algorithm whose complexity depends
polynomially on the input and output sizes. It is thus important to identify
problems (and polytope representations) for which total polynomial-time
algorithms can be obtained. We offer the first total polynomial-time algorithm
for computing the edge-skeleton (including vertex enumeration) of a polytope
given by an optimization or separation oracle, where we are also given a
superset of its edge directions. We also offer a space-efficient variant of our
algorithm by employing reverse search. All complexity bounds refer to the
(oracle) Turing machine model. There is a number of polytope classes naturally
defined by oracles; for some of them neither vertex nor facet representation is
obvious. We consider two main applications, where we obtain (weakly) total
polynomial-time algorithms: Signed Minkowski sums of convex polytopes, where
polytopes can be subtracted provided the signed sum is a convex polytope, and
computation of secondary, resultant, and discriminant polytopes. Further
applications include convex combinatorial optimization and convex integer
programming, where we offer a new approach, thus removing the complexity's
exponential dependence in the dimension.
