$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

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

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?

up vote 5 down vote accepted

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

enter image description here

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

enter image description here

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? – Boson Feb 12 '16 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. – Erel Segal-Halevi Feb 12 '16 at 13:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.