  This paper presents a new algorithm for the convex hull problem, which is
based on a reduction to a combinatorial decision problem
POLYTOPE-COMPLETENESS-COMBINATORIAL, which in turn can be solved by a
simplicial homology computation. Like other convex hull algorithms, our
algorithm is polynomial (in the size of input plus output) for simplicial or
simple input. We show that the ``no''-case of
POLYTOPE-COMPLETENESS-COMBINATORIAL has a certificate that can be checked in
polynomial time (if integrity of the input is guaranteed).
