# Partitioning a rectangle without harming inner rectangles

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

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.

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?

• 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? Feb 12, 2016 at 12:35
• @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. Feb 12, 2016 at 13:39