Algorithms for minimum length partitions of polygons (Q1102107)

We show that it is possible to find a diagonal partition of any n-vertex simple polygon into smaller polygons, each of at most m edges, minimizing the total length of the partitioning diagonals, in time \(O(n^ 3 m^ 2)\). We derive the same asymptotic upper time-bound for minimum length diagonal partitions of simple polygons into exactly m-gons provided that the input polgyon can be partitioned into m-gons. Also, in the latter case, if the input polygon is convex, we can reduce the upper time-bound to \(O(n^ 3 \log m)\).