Approximation for minimum triangulations of simplicial convex 3-polytopes (Q5955142)

For a general simplicial 3-polytope with \(n > 12\) vertices, a triangulation can be found with at most \(n- 10\) tetrahedra, and, in general, this bound is best possible. (Just pick a vertex of the polytope with maximal degree in the edge graph, and triangulate looking from it at the faces in the antistar.) On the other hand, if the polytope is stacked, then \(n-3\) tetrahedra suffice. In this paper, the authors describe a triangulation algorithm, with approximation ratio \(2-\Omega(1/\sqrt{n})\) to the best possible; obviously, this bound cannot be (much) improved, and, in fact, they show that it is optimal for algorithms based purely on the combinatorial type.