Guillotine partition

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 paper guillotine.

There are various optimization problems related to guillotine partition, such as: minimizing the number of rectangles or the total length of cuts.

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.

The algorithm uses dynamic programming based on the following observation: there exists a minimum-length guillotine rectangular partition in which every maximal line segment contains a vertex of the boundary.

In the special case in which all holes are degenerate (single points), the minimum-length guillotine rectangular partition is at most 2 times the minimum-length rectangular partition.

[3] Therefore, the guillotine partition provides a constant-factor approximation to the general problem, which is NP-hard.

These results can be extended to a d-dimensional box: a guillotine-partition with minimum edge-length can be found in time

[4] Arora[5] and Mitchell[6] used the guillotine-partitioning technique to develop polynomial-time approximation schemes for various geometric optimization problems.

Besides the computational problems, guillotine partitions were also studied from a combinatorial perspective.