Partitioning a rectangle without harming inner rectangles

Question

$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:

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:

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?

Answer 1

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.

---

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$:

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

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 and Eppstein 2009, pages 3-5 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?