However this is not always the best possible triangulation. The cube can be divided into only five tetrahedra if we triangulate it a different way, by cutting off every other vertex. The tetrahedron in the middle is regular.
Is there an efficient algorithm for finding the minimum number of tetrahedra needed to triangulate a polyhedron? Is it always safe to cut off degree-three vertices until no more are left, and if so what should be done when none are left? Unfortunately, de Loera et al recently proved that this minimum-complexity triangulation problem is NP-complete.
Nevertheless, the problem has some connections to a still-open problem on binary trees studied by Sleator, Tarjan, and Thurston. They showed that if one changes one tree to another using a standard operation called rotation, this corresponds to a triangulation of a certain polyhedron in which each rotation corresponds to a tetrahedron. Their results on the tree rotation problem can be interpreted as meaning that some polyhedra require as many as 2n-10 tetrahedra, the number that would be generated by connecting everything to one vertex. The rotation-distance triangulation is topological (an abstract simplicial complex) while the NP-completeness proof relies on the geometric configuration of the polyhedron vertices, so does not seem to shed light on this problem.
If three dimensions isn't hard enough, one can always ask similar questions in higher dimensions. The answers aren't known even for such simple shapes as hypercubes. The connect-to-one-vertex strategy still works, and generates d! simplices. Just as in three dimensions, one can do a little better, but not much better: the best known triangulations are still within a single-exponential factor of d!. On the other hand, the best lower bounds known are that the number of simplices must at least be within a single-exponential factor of sqrt d!. So there's still a pretty big gap to close.