Korea Institute for Advanced Study

Minimum Partition of Polygons under Width and Cut Constraints

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 lengt...