Approximating the minimum triangulation of convex 3-polytopes with bounded degrees (Q2387200)

Triangulating 3-polytopes with the \textit{CutPull} method of \textit{F. Y. L. Chin, S. P. Y. Fung}, and \textit{C.-A. Wang} [Discrete Comput. Geom. 26, No. 4, 499--511 (2001; Zbl 1021.52011)] yields a certain approximation ratio \(r\) to the minimal triangulation. Upper bounds for \(r\) derived in the present paper are: \(r=3/2\) in the case of no 3-cycles and all vertex degrees \(\geq 5\); \(r=2-2/12\) in the case of all vertex degrees \(\geq 5\); \(r=2-2/(\Delta+1)-\Omega(\Delta/n)\) in the case of \(n\) vertices and vertex degrees \(\leq\Delta\). Further, any algorithm which considers only the combinatorial structure of a convex polytope cannot give an approximation ratio better than \(r=2-O(1/\Delta)-O(\Delta/n)\).