Decompositions and boundary coverings of non-convex fat polyhedra (Q1037773)

The authors discuss the tetrahedralizations and more general convex decompositions of \(3\)-dimensional polyhedra. It is known that any polyhedron with \(n\) vertices can be decomposed into \(O(n^2)\) tetrahedra, and this estimate is optimal [cf. \textit{B. Chazelle}, SIAM J. Comput. 13, 488--507 (1984; Zbl 0545.68031), \textit{J. Ruppert} and \textit{R. Seidel}, Discrete Comput. Geom. 7, No.~3, 227--253 (1992; Zbl 0747.52009)]. The problem is to describe some general classes of ``realistic'' polyhedra that can be decomposed into fewer than a quadratic number of pieces. Two kinds of polyhedra are considered. A polyhedron \(P\) is said to be fat (locally fat) if for every ball \(B\) which is centered inside \(P\) and does not contain \(P\) the volume of \(B\cap P\) (the volume of the component of \(B\cap P\) that contains the center of \(B\)) is greater than or equal to \(\gamma\cdot Vol(B)\), where \(\gamma\) is some fixed constant [cf. \textit{M. De Berg}, Discrete Comput. Geom. 40, No.~1, 127--140 (2008; Zbl 1158.68048), \textit{A. F. van der Stappen}, J. Intell. Robot. Syst. 11, No.~1--2, 21--44 (1994; Zbl 0816.68127)]. The polyhedron \(P\) is called (\(\alpha\), \(\beta\))-covered if the following condition is satisfied: for each point \(p\in\partial P\) there is a tetrahedron \(T_p\subset P\) with one vertex at \(p\) that is \(\alpha\)-fat and has minimum edge length \(\beta\cdot diam (P)\) [cf. \textit{A. Efrat}, SIAM J. Comput. 34, No.~4, 775--787 (2005; Zbl 1079.65019)]. The first class is strictly more general than the second one: any polyhedron which is (\(\alpha\), \(\beta\))-covered for some \(\alpha\), \(\beta\) is also locally-\(\gamma\)-fat for some constant \(\gamma\) depending on \(\alpha\), \(\beta\). The main result states the following: {\parindent5mm \begin{itemize}\item[1)] there are (\(\alpha\), \(\beta\))-covered polyhedra with \(n\) vertices such that any decomposition into convex pieces uses \(\Omega(n^2)\) pieces; \item[2)] any locally-fat polyhedron with \(n\) vertices whose faces are convex and fat can be decomposed into \(O(n)\) tetrahedra in \(O(n\log n)\) time; \item[3)] there are (\(\alpha\), \(\beta\))-covered polyhedra with \(n\) vertices and convex fat faces such that the number of tetrahedra in any covering that only uses fat tetrahedra can not be bounded as a function of \(n\); \item[4)] the boundary of any (\(\alpha\), \(\beta\))-covered polyhedron can be covered by \(O(n^2\log n)\) fat convex constant-complexity polyhedra, and there are (\(\alpha\), \(\beta\))-covered polyhedra that require \(\Omega(n^2)\) convex pieces in any boundary covering; \item[5)] the boundary of any (\(\alpha\), \(\beta\))-covered polyhedron can be covered by \(O(1/(\alpha\beta)^5)\) towers [see \textit{B. Aronov, M. de Berg} and \textit{C. Gray}, Comput. Geom. 41, No.~1--2, 68--76 (2008; Zbl 1161.68050)] with \(O(1/\alpha ) \) canonical directions. \end{itemize}}