Guillotine partition

Guillotine partition is the process of partitioning a <a href="/facts/Rectilinear_polygon/gV7lyUlA">rectilinear polygon</a>, possibly containing some holes, into rectangles, using only guillotine-cuts. A guillotine-cut (also called an edge-to-edge cut) is a straight bisecting line going from one edge of an existing polygon to the opposite edge, similarly to a <a href="/facts/Paper_guillotine/59RJPbsK">paper guillotine</a>.
Guillotine partition is particularly common in designing <a href="/facts/Floorplan_(microelectronics)/31eoJ3MB">floorplans in microelectronics</a>. An alternative term for a guillotine-partition in this context is a slicing partition or a slicing floorplan. Guillotine partitions are also the underlying structure of <a href="/facts/Binary_space_partitioning/sn9MhTSB">binary space partitions</a>. There are various <a href="/facts/Optimization_problem/QzwJfFEE">optimization problems</a> related to guillotine partition, such as: minimizing the number of rectangles or the total length of cuts. These are variants of <a href="/facts/Polygon_partition/LvpV1moS">polygon partitioning</a> problems, where the cuts are constrained to be guillotine cuts.
A related but different problem is <a href="/facts/Guillotine_cutting/d2wEn9Rj">guillotine cutting</a>. In that problem, the original sheet is a plain rectangle without holes. The challenge comes from the fact that the dimensions of the small rectangles are fixed in advance. The optimization goals are usually to maximize the area of the produced rectangles or their value, or minimize the waste or the number of required sheets.

Guillotine partition open-in-new

Guillotine partition