ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
Mark Keil, Jack Scott Snoeyink · International Journal of Computational Geometry & Applications · 2002
We show that a decomposition of a simple polygon having n vertices, r of which are reflex, into a minimum number of convex regions without the addition of Steiner vertices can be computed in O(n + r2 min {r2, n}) time and space. A Java demo is available at .