math_groups_discgeom

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
Datum2004
Quelle/n
Erschienen inJ. Symbolic Computation (special issue for ICMS 2002), volume 38, pages 1247-1259
ArtText