Minimum Partition of Polygons under Width and Cut Constraints

Abstract

We study the problem of partitioning a polygon into the minimum number of subpolygons using cuts in a fixed set of directions such that each resulting subpolygon satisfies a given width constraint. A polygon satisfies the unit-width constraint for a set of directions if the length of its orthogonal projection onto a line parallel to at least one of those directions is at most one. We analyze structural properties of the minimum number of pieces, focusing on monotonicity under polygon containment. Understanding this monotonicity is a crucial step toward designing efficient exact or approximation algorithms, as it dictates whether subproblems behave well under geometric decomposition. We show that the minimum partition number of a simple polygon is at least that of any subpolygon, provided that the subpolygon satisfies a certain orientation-wise convexity with respect to the polygon. As a core implication of this structural behavior, we prove a partition analogue of Bang’s conjecture for convex bodies in the plane: for any partition of a convex body in the plane, the sum of the relative widths of all parts is at least one. We also show that every convex polygon admits an optimal partition by parallel cuts. Moreover, given a convex polygon with n vertices in boundary order, an optimal partition into m pieces can be computed in $$O(m\log (1+n/m))$$ time.