An efficient algorithm for finding the CSG representation of a simple polygon (Q1261285)

The computer representation of solid objects is discussed. A constructive solid geometry representation (CSG) models a geometric object as a boolean combination of simpler objects. The authors give an \(O(n\log n)\)- time algorithm for converting a given boundary-representation of a polygon into a CSG-representation. For polygons a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once is given (a monotone boolean formula that uses each literal once -- a Peterson-style formula). The authors discuss properties of polyhedrons in 3-space, for which such a Peterson- style-formula exists and show that such nice formulae do not always exist in three dimensions.