Pseudo-Convex Decomposition of Simple Polygons
Stefan Gerdjikov, Alexander Wolff · 2006
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 decomposition with fewer polygons, especially if the original polygon has long chains of concave vertices.