The Complexity of Finding Small Triangulations of Convex 3-Polytopes
arXiv:math/0012177
Abstract
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