DECOMPOSING THE BOUNDARY OF A NONCONVEX POLYHEDRON

We show that the boundary of a three-dimensional polyhedron with r ref lex angles and arbitrary genus can be subdivided into O(r) connected p ieces, each of which lies on the boundary of its convex hull. A remark able feature of this result is that the number of these convex-like pi eces is independent of the number of vertices. Furthermore, it is line ar in r, which contrasts with a quadratic worst-case lower bound in th e number of convex pieces needed to decompose the polyhedron itself. T he number of new vertices introduced in the process is O(n). The decom position can be computed in O(n + r log r) time.