Decompositions and boundary coverings of non-convex fat polyhedra

M. Berg, de, C.M. Gray

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)


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 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.
Original languageEnglish
Pages (from-to)73-83
JournalComputational Geometry
Issue number2
Publication statusPublished - 2010


Dive into the research topics of 'Decompositions and boundary coverings of non-convex fat polyhedra'. Together they form a unique fingerprint.

Cite this