The Complexity of Finding Small Triangulations of Convex 3-Polytopes

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The problem of finding a triangulation of a convex three-dimensional polytope with few tetrahedra is proved to be NP-hard. We discuss other related complexity results.
37 pages. An earlier version containing the sketch of the proof appeared at the proceedings of SODA 2000

Keywords

Combinatorics, Metric Geometry, 52B; 52C45; 68Q

Citation

URI

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

Consulte el texto completo en el siguiente enlace:

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

Collections

arXiv