Approximation for minimum triangulation of convex polyhedra
F. Y. L. Chin, Stanley P. Y. Fung, C. A. Wang · 2001
The minimum triangulation of a convex polyhedron is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding the minimum triangulation of convex polyhedra was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper, we give a new triangulation algorithm with an improved approximation ratio 2 - O(1/√n). We also show that this is best possible for algorithms that only consider the combinatorial structure of the polyhedra.