Pseudo-Convex Decomposition of Simple Polygons

We extend a dynamic-programming algorithm of Keil and Snoeyink for finding a minimum convex decomposition of a simple polygon to the case when both convex polygons and pseudo-triangles are allowed. Our algorithm determines a minimum pseudo-convex decomposition of a simple polygon in O(n 3 ) time where n is the number of the vertices of the polygon. In this way we obtain a well-structured decomposi…