Khan, Arindam ;
Pittu, Madhusudhan Reddy
On Guillotine Separability of Squares and Rectangles
Abstract
Guillotine separability of rectangles has recently gained prominence in combinatorial optimization, computational geometry, and combinatorics. Consider a given large stock unit (say glass or wood) and we need to cut out a set of required rectangles from it. Many cutting technologies allow only endtoend cuts called guillotine cuts. Guillotine cuts occur in stages. Each stage consists of either only vertical cuts or only horizontal cuts. In kstage packing, the number of cuts to obtain each rectangle from the initial packing is at most k (plus an additional trimming step to separate the rectangle itself from a waste area). Pach and Tardos [Pach and Tardos, 2000] studied the following question: Given a set of n axisparallel rectangles (in the weighted case, each rectangle has an associated weight), cut out as many rectangles (resp. weight) as possible using a sequence of guillotine cuts. They provide a guillotine cutting sequence that recovers 1/(2 log n)fraction of rectangles (resp. weights). Abed et al. [Fidaa Abed et al., 2015] claimed that a guillotine cutting sequence can recover a constant fraction for axisparallel squares. They also conjectured that for any set of rectangles, there exists a sequence of axisparallel guillotine cuts that recovers a constant fraction of rectangles. This conjecture, if true, would yield a combinatorial O(1)approximation for Maximum Independent Set of Rectangles (MISR), a longstanding open problem. We show the conjecture is not true, if we only allow o(log log n) stages (resp. o(log n/log log n)stages for the weighted case). On the positive side, we show a simple O(n log n)time 2stage cut sequence that recovers 1/(1+log n)fraction of rectangles. We improve the extraction of squares by showing that 1/40fraction (resp. 1/160 in the weighted case) of squares can be recovered using guillotine cuts. We also show O(1)fraction of rectangles, even in the weighted case, can be recovered for many special cases of rectangles, e.g. fat (bounded width/height), δlarge (large in one of the dimensions), etc. We show that this implies O(1)factor approximation for Maximum Weighted Independent Set of Rectangles, the weighted version of MISR, for these classes of rectangles.
BibTeX  Entry
@InProceedings{khan_et_al:LIPIcs:2020:12650,
author = {Arindam Khan and Madhusudhan Reddy Pittu},
title = {{On Guillotine Separability of Squares and Rectangles}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {47:147:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12650},
URN = {urn:nbn:de:0030drops126505},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.47},
annote = {Keywords: Guillotine cuts, Rectangles, Squares, Packing, kstage packing}
}
11.08.2020
Keywords: 

Guillotine cuts, Rectangles, Squares, Packing, kstage packing 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 