Tetrahedral mesh generation for solids based on alternating sum of volumes

Decomposition of a three-dimensional non-convex polyhedral object into tetrahedra using few or no `Steiner' points assumes both theoretical and practical importance. It has been known that the determination of whether a polyhedron can be tetrahedralized is NP-complete. This prompts the investigation of the tetrahedralization of special classes of polyhedra, including convex, star-shaped, monotone, and isothetic. This paper identifies a special class of polyhedra that can be tetrahedralized without using `Steiner' points. The proposed tetrahedralization algorithm utilizes a structure provided by the alternating sum of volumes process (a convex decomposition method) so that a complex solid object can first be decomposed into a set of simpler objects, namely conjuncts. The concatenation of the tetrahedralization of these conjuncts gives rise to the tetrahedralization of the original solid object.