Share with your friends
hdshahin01

Call

Guillotine partition is the process of partitioning a rectilinear polygon, possibly containing some holes, into rectangles, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing polygon to the opposite edge, similarly to a paper guillotine.

Guillotine partition is particularly common in designing floorplans in microelectronics. 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 binary space partitions. There are various optimization problems related to guillotine partition, such as: minimizing the number of rectangles or the total length of cuts. These are variants of polygon partitioning problems, where the cuts are constrained to be guillotine cuts.

A related but different problem is guillotine cutting. 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.