Decompositions and boundary coverings of non-convex fat polyhedra

M. Berg, de, C.M. Gray

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)
EditorsD. Halperin, K. Mehlhorn
Place of PublicationBerlin
ISBN (Print)978-3-540-87743-1
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


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

Cite this