A tale on guillotine cut
Mihaela Cardei, Xiuzhen Cheng, Xiaoyan Cheng, Ding‐Zhu Du · 2003
Abstract. The guillotine cut is an important tool to design polynomialtime approximation schemes for geometric optimization problems. In this article, we survey its history and recent developments. 1 Guillotine Cut Robespirre (1758-1794) introduced the guillotine cut in French revolution. Nowadays, the guillotine cut has become an important technique to design PTAS (polynomialtime approximation schemes) for geometric optimization problems. Roughly speaking, a guillotine cut is a subdivision with a line which divides given area into at least two subarea. To make our expanation more meaningful, let us consider a specific problem. The minimum edge-length rectangular partition (MELRP) was first proposed by Lingas, Pinter, Rivest, and Shamir [15]. It can be stated as follows: Given a rectilinear polygon possibly with some rectangular holes, partition it into rectangles with minimum total edge-length. The holes in the input rectangular polygon can be, possibly in part, degenerated into a line segment or a point (Fig. 1).