DETERMINING THE CASTABILITY OF SIMPLE POLYHEDRA

A polyhedron P is castable if its boundary can be partitioned by a pla ne into two polyhedral terrains. Castable polyhedra can be manufacture d easily using two cast parts, where each cast part can be removed fro m the object without breaking the cast part or the object. If we assum e that the cast parts are each removed by a single translation, it is shown that for a simple polyhedron with n vertices, castability can be decided in O(n(2)log n) time and linear space using a simple algorith m. A more complicated algorithm selves the problem in O(n(3/2+epsilon) ) time and space, for any fixed epsilon > 0. In the case where, the ca st parts are to be removed in opposite directions, a simple O(n(2))-ti me algorithm is presented. Finally, if the object is a convex polyhedr on and the cast parts are to be removed in opposite directions, a simp le O(n log(2) n) algorithm is presented.