Decompositions and boundary coverings of non-convex fat polyhedra

We show that any locally-fat (or (a, ß)-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 O(n2) pieces in any convex decomposition. Furthermore, we show that if we want the polyhedra in the decomposition to be fat themselves, then the worst-case number of tetrahedra cannot be bounded as a function of n. Finally, we obtain several results on the problem where we want to only cover the boundary of the polyhedron, and not its entire interior.