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.
|Title of host publication||Algorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)|
|Editors||D. Halperin, K. Mehlhorn|
|Place of Publication||Berlin|
|Publication status||Published - 2008|
|Name||Lecture Notes in Computer Science|