We study the problem of cutting a simple polygon with n vertices into two pieces such that - if we reposition one piece disjoint of the other, without rotation - they have the minimum possible bounding square. If we cut with a single horizontal or vertical segment, then we can compute an optimal solution for a convex polygon with n vertices in O(n) time. For simple polygons we give an O(n~4α(n) log n) time algorithm.
展开▼
