<p>NEW ANSWER: the following simple algorithm is asymptotically optimal:</p>

<blockquote>
  <p>Stretch each of the rectangles <span class="math-container">$C_i$</span> arbitrarily, to the maximal extent possible such that the rectangles remain pairwise-disjoint.</p>
</blockquote>

<p>The number of holes is at most <span class="math-container">$k-2$</span>. This is asymptotically optimal, as there are configurations in which the number of holes is at least <span class="math-container">$k-O(\sqrt k)$</span>.</p>

<p>The proofs are in <a href="https://epubs.siam.org/doi/abs/10.1137/16M110407X" rel="nofollow noreferrer">this paper</a>.</p>

<hr>

<p>OLD ANSWER:</p>

<p>The following algorithm, while not optimal, is apparently sufficient for finding a rectangle-preserving partition with <span class="math-container">$N=O(n)$</span> parts.</p>

<p>The algorithm works with a rectilinear polygon <span class="math-container">$P$</span>, which is initialized to the rectangle <span class="math-container">$C$</span>.</p>

<p><strong>Phase 1:</strong> Pick a rectangle <span class="math-container">$C_i$</span> which is adjacent to a western boundary of <span class="math-container">$P$</span> (i.e, there is no other rectangle <span class="math-container">$C_j$</span> between the western side of <span class="math-container">$C_i$</span> and a western boundary of <span class="math-container">$P$</span>). Place <span class="math-container">$C_i$</span> within <span class="math-container">$P$</span> and stretch it until it touches the western boundary of <span class="math-container">$P$</span>. Let <span class="math-container">$E_i$</span> (for <span class="math-container">$i=1,\dots,n$</span>) be the stretched version of <span class="math-container">$C_i$</span>. Let <span class="math-container">$P=P\setminus E_i$</span>. Repeate Phase 1 <span class="math-container">$n$</span> times until all <span class="math-container">$n$</span> original rectangles are placed and stretched. In the image below, a possible order of placing the rectangles is <span class="math-container">$C_1,C_2,C_4,C_3$</span>:</p>

<p><a href="https://i.sstatic.net/KHiTu.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/KHiTu.png" alt="enter image description here"></a></p>

<p>Now, <span class="math-container">$P$</span> is a rectilinear polygon (possibly disconnected), like this:</p>

<p><a href="https://i.sstatic.net/4cANr.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/4cANr.png" alt="enter image description here"></a></p>

<p>I claim that the number of <em>concave vertices</em> in <span class="math-container">$P$</span> is at most <span class="math-container">$2n$</span>. This is because, whenever a stretched rectangle is removed from <span class="math-container">$P$</span>, there are 3 possibilities:</p>

<ul>
<li>2 new concave vertices are added (like when placing <span class="math-container">$C_1,C_4$</span>);</li>
<li>3 new concave vertices are added and 1 is removed (like with <span class="math-container">$C_3$</span>);</li>
<li>4 new concave vertices are added and 2 are removed (like with <span class="math-container">$C_2$</span>).</li>
</ul>

<p><strong>Phase 2:</strong> Partition <span class="math-container">$P$</span> into axis-parallel rectangles using an existing algorithm (see <a href="https://mpen.ca/406/files/PolygonDecomp-Keil.pdf" rel="nofollow noreferrer">Keil 2000, pages 10-13</a> and <a href="http://arxiv.org/pdf/0908.3916.pdf" rel="nofollow noreferrer">Eppstein 2009, pages 3-5</a> for a review).</p>

<p>Keil cites a theorem that says that the number of rectangles in a minimal partition is bounded by 1 + the number of concave vertices. Hence, in our case the number is at most <span class="math-container">$2n+1$</span>, and the total number of rectangles in the partition is <span class="math-container">$N\leq 3n+1$</span>.</p>

<hr>

<p>This algorithm is not optimal. E.g, in the above example it gives <span class="math-container">$N=13$</span> while the optimal solution has <span class="math-container">$N=5$</span>. So two questions remain:</p>

<p>A. Is this algorithm correct?</p>

<p>B. Is there a polynomial-time algorithm for finding the optimal <span class="math-container">$N$</span>, or at least a better approximation?</p>

CC BY-SA 3.0
2016-02-12T12:35:05.710Z
Well, in phase 1, you add partition cells, each of which contains exactly one initial rectangle and does not overlap on another.
In phase 2, you partition the remaining space, so the cells created in phase 2 do not intersect any of the initial rectangle.
Proof of correctness seems rather straightforward, or did I miss something?
Boson
CC BY-SA 3.0
2016-02-12T13:39:51.833Z
@Boson the point I am not sure at is that the number of concave vertices is at most $2n$. It seems "obvious" that there are only 3 possibilities as I wrote, but I may have missed some other possibility.
Erel Segal-Halevi
CC BY-SA 4.0
2016-02-12T11:33:30.377Z
2018-11-18T06:06:12.073Z
2018-11-18T06:06:12.073Z
Erel Segal-Halevi
<p>$C$ is an axis-parallel rectangle. </p>

<p>$C_1,\dots,C_n$ are pairwise-interior-disjoint axis-parallel rectangles such that $C_1\cup\dots\cup C_n \subsetneq C$, like this:</p>

<p><a href="https://i.sstatic.net/e5Tcm.png" rel="noreferrer"><img src="https://i.sstatic.net/e5Tcm.png" alt="enter image description here"></a></p>

<p>A <strong>rectangle-preserving partition</strong> of $C$ is a partition $C = E_1\cup\dots\cup E_N$, such that $N\geq n$, the $E_i$ are pairwise-interior-disjoint axis-parallel rectangles, and for every $i=1,\dots,n$: $C_i \subseteq E_i$, i.e, each existing rectangle is contained in a unique new rectangle, like this:</p>

<p><a href="https://i.sstatic.net/7HSLm.png" rel="noreferrer"><img src="https://i.sstatic.net/7HSLm.png" alt="enter image description here"></a></p>

<p>What is an algorithm for finding a rectangle-preserving partition with a small $N$? </p>

<p>In particular, is there an algorithm for finding a rectangle-preserving partition with $N=O(n)$ parts?</p>

<cg.comp-geom>
Partitioning a rectangle without harming inner rectangles
Erel Segal-Halevi
# Partitioning a rectangle without harming inner rectangles

(Asked by: username_0 on 2016-02-06)

$C$ is an axis-parallel rectangle.

$C\_1,\dots,C\_n$ are pairwise-interior-disjoint axis-parallel rectangles such that $C\_1\cup\dots\cup C\_n \subsetneq C$, like this:

[![enter image description here](https://i.sstatic.net/e5Tcm.png)](https://i.sstatic.net/e5Tcm.png)

A **rectangle-preserving partition** of $C$ is a partition $C = E\_1\cup\dots\cup E\_N$, such that $N\geq n$, the $E\_i$ are pairwise-interior-disjoint axis-parallel rectangles, and for every $i=1,\dots,n$: $C\_i \subseteq E\_i$, i.e, each existing rectangle is contained in a unique new rectangle, like this:

[![enter image description here](https://i.sstatic.net/7HSLm.png)](https://i.sstatic.net/7HSLm.png)

What is an algorithm for finding a rectangle-preserving partition with a small $N$?

In particular, is there an algorithm for finding a rectangle-preserving partition with $N=O(n)$ parts?

**Tags:** cg.comp-geom

---

## 1 answers

### Answer by username_0 on 2016-02-12. Score: 4 | Accepted answer

NEW ANSWER: the following simple algorithm is asymptotically optimal:

> Stretch each of the rectangles $C\_i$ arbitrarily, to the maximal extent possible such that the rectangles remain pairwise-disjoint.

The number of holes is at most $k-2$. This is asymptotically optimal, as there are configurations in which the number of holes is at least $k-O(\sqrt k)$.

The proofs are in [this paper](https://epubs.siam.org/doi/abs/10.1137/16M110407X).

---

OLD ANSWER:

The following algorithm, while not optimal, is apparently sufficient for finding a rectangle-preserving partition with $N=O(n)$ parts.

The algorithm works with a rectilinear polygon $P$, which is initialized to the rectangle $C$.

**Phase 1:** Pick a rectangle $C\_i$ which is adjacent to a western boundary of $P$ (i.e, there is no other rectangle $C\_j$ between the western side of $C\_i$ and a western boundary of $P$). Place $C\_i$ within $P$ and stretch it until it touches the western boundary of $P$. Let $E\_i$ (for $i=1,\dots,n$) be the stretched version of $C\_i$. Let $P=P\setminus E\_i$. Repeate Phase 1 $n$ times until all $n$ original rectangles are placed and stretched. In the image below, a possible order of placing the rectangles is $C\_1,C\_2,C\_4,C\_3$:

[![enter image description here](https://i.sstatic.net/KHiTu.png)](https://i.sstatic.net/KHiTu.png)

Now, $P$ is a rectilinear polygon (possibly disconnected), like this:

[![enter image description here](https://i.sstatic.net/4cANr.png)](https://i.sstatic.net/4cANr.png)

I claim that the number of *concave vertices* in $P$ is at most $2n$. This is because, whenever a stretched rectangle is removed from $P$, there are 3 possibilities:

* 2 new concave vertices are added (like when placing $C\_1,C\_4$);
* 3 new concave vertices are added and 1 is removed (like with $C\_3$);
* 4 new concave vertices are added and 2 are removed (like with $C\_2$).

**Phase 2:** Partition $P$ into axis-parallel rectangles using an existing algorithm (see [Keil 2000, pages 10-13](https://mpen.ca/406/files/PolygonDecomp-Keil.pdf) and [Eppstein 2009, pages 3-5](http://arxiv.org/pdf/0908.3916.pdf) for a review).

Keil cites a theorem that says that the number of rectangles in a minimal partition is bounded by 1 + the number of concave vertices. Hence, in our case the number is at most $2n+1$, and the total number of rectangles in the partition is $N\leq 3n+1$.

---

This algorithm is not optimal. E.g, in the above example it gives $N=13$ while the optimal solution has $N=5$. So two questions remain:

A. Is this algorithm correct?

B. Is there a polynomial-time algorithm for finding the optimal $N$, or at least a better approximation?

> **Comments:**
> **username_1**: Well, in phase 1, you add partition cells, each of which contains exactly one initial rectangle and does not overlap on another. In phase 2, you partition the remaining space, so the cells created in phase 2 do not intersect any of the initial rectangle. Proof of correctness seems rather straightforward, or did I miss something?  
> **username_0**: @Boson the point I am not sure at is that the number of concave vertices is at most $2n$. It seems "obvious" that there are only 3 possibilities as I wrote, but I may have missed some other possibility.  

---

