Convex Decomposition of Simple Polygons

An algorithm is described for the decomposition of a bounded concave region of E2 space into a settheoretic combination of convex regions. This algorithm finds the convex hull of the region and then recurses to find the convex hulls of the difference between the original region and its convex hull, until such regions are convex. It exhibits a linear-time complexity for regions whose difference with their convex hull consists of only convex inner regions, a quadratic worst-case complexity, and an average complexity a little worse than linear.