Springe direkt zu Inhalt

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

Titel
Convex hulls, oracles, and homology
Verfasser
Michael Joswig and Günter M. Ziegler
Datum
2004
Erschienen in
J. Symbolic Computation (special issue for ICMS 2002), volume 38, pages 1247-1259
Art
Text