Minimum convex partition of polygonal domains by guillotine cuts (Q1380781): Difference between revisions

Suppose that you have a piece of plywood, which you want to cut neatly into pieces using a hand-held circular saw. Because of the position of the blade a cut made with such a tool cannot be stopped neatly except at a boundary; so you are restricted to so-called guillotine cuts -- an ordered sequence of linear cuts, each beginning and ending either at an edge or a previously made cut. There are also situations (e.g., ripping cloth) in which feasible cuts are also restricted to certain directions. In this paper, the authors consider the problem of cutting a polygonal region, possibly with holes (which may be punctures, slits, or polygons) into a minimum number of convex pieces, using guillotine cuts which may be constrained to a certain set of directions. An exact formula is given for the minimum number of pieces in such a partition. The formula is surprisingly simple, though some subtleties are involved in the definition of the ``effective number'' of a polygonal region.