when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-126505
URL:

;

### On Guillotine Separability of Squares and Rectangles

 pdf-format:

### 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 end-to-end cuts called guillotine cuts. Guillotine cuts occur in stages. Each stage consists of either only vertical cuts or only horizontal cuts. In k-stage 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 axis-parallel 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 axis-parallel squares. They also conjectured that for any set of rectangles, there exists a sequence of axis-parallel 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 long-standing 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 2-stage cut sequence that recovers 1/(1+log n)-fraction of rectangles. We improve the extraction of squares by showing that 1/40-fraction (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:1--47:22},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-164-1},
ISSN =	{1868-8969},
year =	{2020},
volume =	{176},
editor =	{Jaros{\l}aw Byrka and Raghu Meka},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address =	{Dagstuhl, Germany},
URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12650},
URN =		{urn:nbn:de:0030-drops-126505},
doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.47},
annote =	{Keywords: Guillotine cuts, Rectangles, Squares, Packing, k-stage packing}
}
```

 Keywords: Guillotine cuts, Rectangles, Squares, Packing, k-stage packing Seminar: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) Issue date: 2020 Date of publication: 11.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy