Generalised Bagemihl polyhedra and a tight bound on the number of interior Steiner points

We call a 3d polyhedron irreducible if it cannot be decomposed into a set of convex polytopes without adding additional vertices, called Steiner points. Such polyhedra are primitive shapes which are the essence of the reason that will force any 3d convex decomposition algorithm to insert Steiner points in its interior. In this paper, we construct a class of 3d irreducible polyhedra, called generalised Bagemihl polyhedra, with n≥6 vertices. We show that such polyhedra have the same combinatorial structure as the Schönhardt and Bagemihl polyhedra. The most interesting property of these polyhedra is that one can construct it in such a way that it will need more than one interior Steiner point to be triangulated. Given a generalised Bagemihl polyhedron with n≥6 vertices, we show that it can be triangulated by adding at most n−52 interior Steiner points. Moreover, this number is tight. We show an application of using these polyhedra to evaluate the quality of existing 3d boundary recovery tetrahedralisation algorithms.