An Improved Guillotine Cut for Squares

Our results relate to a dynamic programming framework for geometric packing, initiated by Adamaszek and Wiese [3, 2]. Their framework is parametrized by $(\alpha ,t)$, where a geometric object family is called $(\alpha ,t)$-good if it contains a subset of at least an $\alpha$-fraction of objects that can be separated using polygonal cuts that always create pieces with at most $t$ edges. If a family is $(\alpha ,t)$-good, the framework yields a $(1/\alpha )$-approximation algorithm with running time $n^{O(t)}$. In Adamaszek, Har-Peled, and Wiese’s elegant result [2], they show that every family of polygons in 2D is $((1-ϵ),poly\log n)$-good, implying a quasi-polynomial time approximation scheme (QPTAS) for the independent set of polygons.

Since the existence of a $\gamma$-fraction guillotine separable subset implies that the family is $(\gamma ,4)$-good, our results directly contribute to a better understanding of this framework for squares. The recent breakthrough by Mitchell [14] show that rectangles are $(1/10,5)$-good, and further refinements [11] prove that they are $(\frac{1}{2}-ϵ,O(1/ϵ))$-good, leading to the best known $(2+ϵ)$-approximation algorithm for the maximum independent set of rectangles.

We prove it by induction on the size of $G_1$. If $G_1$ is empty, it is obviously $15$-colorable. Otherwise, we take the smallest non-empty cell $C_1$ such that ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}(C_1)\ne \mathrm{\varnothing }$, i.e. there exists a square $S\in {ℛ}_1$ such that $𝒪𝒞(S)=C_1$, and for any cell $C_2$ contained in $C_1$, we have ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}(C_2)=\mathrm{\varnothing }$. Let $i$ be the level of cell $C_1$.

According to the induction hypothesis, $G_1\backslash {\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}(C_1)$ is $15$-colorable, so let us assume it is already colored. We show that we can color all the squares in ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}(C_1)$ to get a $15$ coloring for $G_1$. These squares all have to have a level at most $i$; otherwise, their original cell would have been smaller, and we wouldn’t have chosen $C_1$. According to Fact 4, the size of level-$i$ squares is strictly bigger than $\frac{1}{2r}=\frac{1}{4}$ of the size of $C_1$, and therefore at most $3$ squares of level $i$ fit into a cell of level $i$ horizontally as well as vertically. Since squares of smaller levels are larger, it follows that at most $9$ squares can be inside $C_1$ (Figure 2). If $C_1$ contains squares of smaller levels, they will already be colored by the induction hypothesis, and these colors will not be changed. We can color all the squares in ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}(C_1)$ with at most nine different colors (see Figure 2), avoiding the already used colors inside $C_1$.

Now, we bound the number of squares that conflict with any square in ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}(C_1)$ but are not contained in $C_1$. Since $C_1$ is the smallest non-empty cell, any square $S\in {ℛ}_1$ must cross the boundary of $C_1$. Since $C_1$ is a level-$i$ cell, then $𝒪𝒞(S)$ is a level-$j$ cell for . We bound the number of squares that can conflict with any square in ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}(C_1)$ based on the way they intersect $C_1$ (see Figure 3(a)): First, there can be at most four squares containing one of the corners of $C_1$. Next, let $S$ be a square intersecting the side of $C_1$ without containing any corner. Using Fact 4, we know that the size of $S$ is strictly bigger than half of the size of $C_1$. Thus, there can be at most one square in this position for each side of $C_1$, which adds up to four squares. We can further reduce this number because two sides of any level-$i$ cell are also level-$(i-1)$ grid lines. Then, there cannot be any intersecting square on those sides, implying that at most two squares intersecting only sides of $C_1$ (see Figure 3(b)).

We showed that at most six squares can conflict with squares in ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}(C_1)$ by intersecting the boundary of $C_1$ and at most $9$ colors can be required to color the squares inside $C_1$, leading to a valid $15$ coloring for $G_1$. $◀$

Let $ℐ\subseteq {ℛ}_1$ be an independent set of $G_1$. First, we can separate the two squares with the “biggest” original cells without cutting through any other squares. Let $S_1,S_2\in ℐ$ be the squares such that $\mathrm{𝗌𝗂𝗓𝖾}(𝒪𝒞(S_1))\ge \mathrm{𝗌𝗂𝗓𝖾}(𝒪𝒞(S_2))$ and for any other square $S\in ℐ$, $\mathrm{𝗌𝗂𝗓𝖾}(𝒪𝒞(S_2))\ge \mathrm{𝗌𝗂𝗓𝖾}(𝒪𝒞(S))$. Note that since $S_1$ and $S_2$ cannot conflict, then $𝒪𝒞(S_1)\ne 𝒪𝒞(S_2)$.

Since the grid lines defining $𝒪𝒞(S_2)$ cannot go through any cell smaller than itself, we can safely cut along these grid lines and do not touch any other squares in $ℐ$ except for $S_1$. Now, we claim that one of the four grid lines defining $𝒪𝒞(S_2)$ separates $S_1$ and $S_2$ (see Figure 4). Since $S_1$ cannot intersect $𝒪𝒞(S_2)$, it must be entirely on the left, right, top, or bottom of $𝒪𝒞(S_2)$. The grid line of the corresponding side then separates $S_1$ from $S_2$ without cutting any square in $ℐ$. We can separate all the squares by recursively and independently applying this process to the two resulting sub-instances. $◀$

The bound $j\le i+1$ is a direct result of the scaling factor: for a cell $C$ of level $i$, $\mathrm{𝗌𝗂𝗓𝖾}(S)>\frac{1}{4}\mathrm{𝗌𝗂𝗓𝖾}(C)$ (Fact 4), therefore for a cell $C_1$ of level $i+1$, we would have $\mathrm{𝗌𝗂𝗓𝖾}(S)>\frac{1}{2}\mathrm{𝗌𝗂𝗓𝖾}(C_1)$ and for a level-$(i+2)$ cell $C_2$, $\mathrm{𝗌𝗂𝗓𝖾}(S)>\mathrm{𝗌𝗂𝗓𝖾}(C_2)$. This implies that $C_2$ cannot be a fitting cell of $S$, bounding $j$ at most $i+1$. The first part of the inequality, $i\le j$, is easy to see since every original cell must contain $S$, so the smallest cell that contains $S$ cannot be larger than $𝒪𝒞(S)$. $◀$

We define the new conflict graph $G_2$ based on the definition of conflicts below.

Figure 6 shows examples of conflicting and non-conflicting squares.

Analogously to ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{𝒪𝒞}$ for original cells, we define ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}$ for fitting cells.

The proof can be found in Appendix A.

The proof can be seen by replacing the concept of original cells in Lemma 9 with fitting cells.

We define the new conflict graph $G_3$ based on the definition of conflicts below.

The proof can be found in Appendix A.

Similarly to Lemma 9, we show a recursive cutting strategy. Starting with an independent set ${ℛ}_2$ of $G_3$, we first separate two squares with the “biggest” fitting cell. Let $S_1,S_2\in {ℛ}_2$ be the squares such that $\mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S_1))\ge \mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S_2))$, and for any other square $S\in {ℛ}_2$, $\mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S_2))\ge \mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S))$. If $ℱ𝒞(S_1)\ne ℱ𝒞(S_2)$, then $S_1$ and $S_2$ can be separated using the proof of Lemma 9 (see Figure 4). Otherwise, $S_1,S_2$ must be twin squares with a common fitting cell (let $C=ℱ𝒞(S_1)$), since they do not conflict. Then, we can cut along the grid lines of $C$ (see Figure 8). Since for any square $S\in {ℛ}_2$, $\mathrm{𝗌𝗂𝗓𝖾}(C)\ge \mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S))$, we can safely perform these cuts without intersecting any square in ${ℛ}_2$.

Let $i$ be the level of $C$. Since we have isolated $C$ with the first $4$ cuts, further cuts of $C$ can be done independently from the rest of the graph. We use the horizontal (or vertical) level-$(i+1)$ grid line, which certifies that $S_1$ and $S_2$ are twins (see Definition 16), as a cut to separate $S_1$ from $S_2$ (see Figure 8). Let $S\in {ℛ}_2$ be any square inside $C$ intersecting the cut. Since $S$ is contained in $C$ then $\mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S))\le \mathrm{𝗌𝗂𝗓𝖾}(C)$. $S$ also cannot have a level-$(i+1)$ (or smaller) cell as its fitting cell because of intersecting the level-$(i+1)$ grid line. Therefore $ℱ𝒞(S)=C$. Since twin squares $S_1$ and $S_2$ intersect the vertical level-$(i+1)$ grid line and their fitting cell is also $C$, then $S$ conflicts with them. This implies that $S\notin {ℛ}_2$ and the cut is safe to perform. Similarly to the proof of Lemma 9, we recursively apply this process to separate ${ℛ}_2$. $◀$

The first part follows directly from Fact 11. Let us consider the second part. When we define fitting cells over ${ℒ}_2$, the surviving set remains the same; therefore, when the fitting cell is a half-cell, it is always two times narrower than if we defined fitting cells over $ℒ$. Similarly to the proof of Fact 11, a half-cell $C$ of level $(i,i+1)$ has $\mathrm{𝗐𝗂𝖽𝗍𝗁}(S)>\frac{1}{2}\mathrm{𝗐𝗂𝖽𝗍𝗁}(C)$, therefore a half-cell $C_1$ of level $(i+1,i+2)$ would not be able to contain $S$. $◀$

Similarly to the original definition Definition 16, we define twin squares $S_1,S_2\in {ℛ}_1$ to be a pair of squares in the same fitting cell $C_1$ (which is a level-$i$ square-cell) that are separated by a level-$(i+1)$ grid line.

If their fitting cell is a half-cell, we do not consider $S_1,S_2\in {ℛ}_1$ twin squares. Additionally, twin squares $S_1,S_2\in {ℛ}_1$ cannot be separated by a vertical grid line, otherwise their fitting cells would be separate half-cells.

We define the new conflict graph $G_4$ based on the same Definition 17 of conflicts with respect to the new fitting cells of ${ℒ}_2$. See Figure 10 for illustration.

This proof is easier to show by using a stronger statement. We will show that there exists an $8$-coloring of $G_4$, such that for each cell $C\in {ℒ}_2$, the squares ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C)$ are colored with at most $2$ colors.

We will see this proof by induction over the number of squares ($|V(G_4)|$). The base case holds trivially. We again pick the smallest non-empty cell $C_1\in {ℒ}_2$ for induction. Then ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)\ne \mathrm{\varnothing }$ and for any cell $C_2$ smaller than $C_1$ ($\mathrm{𝗌𝗂𝗓𝖾}(C_2)\le \mathrm{𝗌𝗂𝗓𝖾}(C_1)$), we have ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_2)=\mathrm{\varnothing }$.

We assume that the induction hypothesis holds for $G_4\setminus {\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$ and show that we can use $2$ colors to color ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$, with at most eight colors in total. We will consider the cases where $C_1$ is a square-cell or a half-cell separately.

Firstly, consider that $C_1$ is a square-cell of level $i$. Equivalently to Lemma 8, it can be seen that there are at most $6$ squares that can conflict with any square in ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$. Since these squares use at most $6$ colors, at least $2$ colors remain to color ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$. We will count the number of squares $C_1$ contains, which, similarly to previous proofs, is the same as ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$ due to how $C_1$ was chosen. All squares in $C_1$ must intersect the vertical grid line of level $i+1$, splitting $C_1$; otherwise, those squares would be contained in a subcell of $C_1$. According to Fact 4, these squares can be at most $3$. These squares can be colored with $2$ colors since the squares above and below the horizontal grid line of the level $i+1$ are twin squares and can share a color (Figure 11).

Secondly, we consider that $C_1$ is a level-$(i,i+1)$ half-cell. Again, the squares that $C_1$ contains among ${ℛ}_1$ are exactly ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$ due to how $C_1$ was chosen. These squares must intersect the horizontal grid line of level $i+1$ within $C_1$; otherwise, they would fit into a subcell of $C_1$. The squares in ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$ must be of level $i$ to have survived, and the number of level-$i$ squares intersecting the level-$(i+1)$ grid line in $C_1$ can be at most $1$ (Fact 21, Fact 4). Since ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$ cannot be empty, it must contain exactly one square. Let $S$ be that square.

It remains to bound the number of squares conflicting with $S$. Note that all the conflicting squares must intersect the boundary of $C_1$ (Definition 17). Let $C_0$ be the level-$i$ square-cell such that $C_1$ is a subcell of $C_0$.

At most, $4$ squares can intersect with the corners of cell $C_1$. Next, consider the squares intersecting the level-$i$ horizontal grid lines bordering $C_1$. For these squares to survive, their level must be at most $i-1$. This implies they are too large to intersect only the level-$i$ horizontal grid line without intersecting a corner (Figure 12). Next, let us consider the level-$i$ vertical grid lines bordering $C_0$. Similarly to Lemma 8, Figure 3(b), one of those grid lines must also be of level $i-1$ and therefore cannot have a surviving square intersecting it without also intersecting a corner. This leaves us with one square $S_1$ as depicted on Figure 12. Finally, let us consider the squares intersecting the level-$(i+1)$ vertical grid line bordering $C_1$ (Figure 12). Since we already counted the squares intersecting the borders of $C_0$ in addition to $C_1$, these squares must be in ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_0)$. By induction hypothesis, they can be colored with $2$ colors. If the colors of the corner squares and $S_1$ are different from these two colors, we have at most $7$ colors used for the set of squares that conflict with $S$. By coloring $S$ with a different color, we have a valid $8$-coloring with at most $2$ colors used for ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C_1)$ as stated. $◀$

Similarly to Lemma 19, we show a recursive cutting strategy. Starting with an independent set ${ℛ}_2$ of $G_4$, we first separate two squares with the “biggest” fitting cell. Let $S_1,S_2\in {ℛ}_2$ be the squares such that $\mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S_1))\ge \mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S_2))$, and for any other square $S\in {ℛ}_2$, $\mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S_2))\ge \mathrm{𝗌𝗂𝗓𝖾}(ℱ𝒞(S))$. If $ℱ𝒞(S_1)\ne ℱ𝒞(S_2)$, then $S_1$ and $S_2$ can be separated using the proof of Lemma 9 (see Figure 4). Next, we consider the case that $ℱ𝒞(S_1)=ℱ𝒞(S_2)$, e.g $S_1$ and $S_2$ share the same fitting cell. Let this fitting cell be $C$ and its level be $i$.

First, consider the case that $C$ is a half-cell. This implies that $S_1$ and $S_2$ intersect the same horizontal grid line of level $i+1$. Otherwise, they would fit in smaller subcells. Since there are no twin squares in half-cells, $S_1$ and $S_2$ conflict, which contradicts them being in the same independent set ${ℛ}_2$.

Secondly, consider the case that $C$ is a square-cell. Similarly to the proof of Lemma 19, the square-cell can be isolated from the rest of the graph by the first $4$ cuts as depicted on Figure 8. Again, these cuts will not intersect any squares outside of $C$, because the fitting cells for other squares must be smaller than or equal to the size of $C$ (due to our choice of $S_1$ and $S_2$). Similarly to Lemma 19, the fifth cut is a level-$(i+1)$ horizontal grid line if $i$ is the level of $C$. Let us now consider the squares inside $C$ since the fifth cut will be performed only on $C$. For ${\mathrm{𝖲𝗊𝗎𝖺𝗋𝖾𝗌}}_{ℱ𝒞}(C)$, we can see similarly to Lemma 19 that they are not cut. For a square $S$ whose fitting cell is a half-cell subcell of $C$, there is a conflict between $S$ and $S_i$, because $ℱ𝒞(S_1)\ge ℱ𝒞(S)$ and $S_1$ intersects $ℱ𝒞(S)$. This means that $S$ cannot exist in the independent set ${ℛ}_2$, and the cutting strategy doesn’t cut any squares.

Similarly to the proof of Lemma 9, we recursively apply this process to separate ${ℛ}_2$. $◀$