Minimum convex partition of polygonal domains by guillotine cuts (Q1380781): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 16:25, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum convex partition of polygonal domains by guillotine cuts |
scientific article |
Statements
Minimum convex partition of polygonal domains by guillotine cuts (English)
0 references
11 March 1998
0 references
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.
0 references
polygons
0 references
dissection
0 references
guillotine cuts
0 references