Decompositions and boundary coverings of non-convex fat polyhedra

We show that any locally-fat (or (α,β)-covered) polyhedron with convex fat faces can be decomposed into O(n) tetrahedra, where n is the number of vertices of the polyhedron. We also show that the restriction that the faces are fat is necessary: there are locally-fat polyhedra with non-fat faces that require Ω(n2) pieces in any convex decomposition. Furthermore, we show that if we want the tetrahedra in the decomposition to be fat themselves, then their number cannot be bounded as a function of n in the worst case. Finally, we obtain several results on the problem where we want to only cover the boundary of the polyhedron, and not its entire interior.