Domain Extension of Isothetic Polyhedra with Minimal CSG Representation

Abstract

We consider the problem of converting boundary representations of isothetic polyhedra into constructive solid geometry (CSG) representations. The CSG representation is a boolean formula based on the half-spaces supporting the faces of the polyhedron. This boolean formula exhibits two important features: no term is complemented (it is monotone) and each supporting half-space appears in the formula once and only once. It is known that such formulas do not always exist for general polyhedra in the three-dimensional space. In this work first we give a procedure that extends the domain of polyhedra for which such a nice representation can be computed. Then we prove that not all cyclic isothetic polyhedra have a CSG representation of the style given above.