On the Time Bound for Convex Decomposition of Simple Polygons

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 + r 2 min {r 2 , n}) time and space. A Java demo is available at .