Convex Hulls, Oracles, and Homology

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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).
11 pages, 2 figures

Keywords

Metric Geometry, Combinatorics, 52B55; 05E25; 68Q25

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/66224

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0301100
 http://arxiv.org/abs/math/0301100

Collections

arXiv