Decompositions and boundary coverings of non-convex fat polyhedra |
| |
Authors: | Mark de Berg Chris Gray |
| |
Institution: | aDepartment of Computing Science, TU Eindhoven, PO Box 513, 5600 MB Eindhoven, The Netherlands;bDepartment of Computer Science, TU Braunschweig, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Decomposition Tetrahedralization Fatness Realistic input models |
本文献已被 ScienceDirect 等数据库收录! |
|