Convex hulls, oracles, and homology

Michael Joswig and Günter M. Ziegler— 2004

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).

TitelConvex hulls, oracles, and homology
VerfasserMichael Joswig and Günter M. Ziegler
Erschienen inJ. Symbolic Computation (special issue for ICMS 2002), volume 38, pages 1247-1259