Maximum number of subrectangles that lie completely within a rectangle

Question

Suppose I have $n$ rectangles in the 2D plane, as shown on the left. I am interested in partitioning the region inside these rectangles into disjoint sub-rectangles and counting the number of resulting subrectangles. Toward that end, I create grid lines along the edges of the rectangles (i.e., $2n$ vertical lines and $2n$ horizontal lines), as shown on the right.

In this specific example, there are $n=5$ rectangles and 81 sub-rectangles in the grid, 58 of which lie in the union of the original $n$ rectangles, shown in yellow below.

In the general case:

1. What is the maximum number of subrectangles that can lie fully inside an original rectangle? A loose upper bound is to observe that there are exactly $(2n-1) \times (2n-1)$ subrectangles in the grid , all of which are disjoint, and each subrectangle is either fully contained in or fully not contained in another rectangle. Is there a tighter bound?

2. What is the naive bound in $d$ dimensions? Is there a tighter bound? Specifically, we are now counting the number of disjoint $d$-dimensional subcubes in the grid that partition $n$ $d$-dimensional cubes?

Answer 1

The maximum possible is in fact $(2n-1)^2$, i.e. the trivial bound is tight. This can be achieved by:

• Having a big rectangle that encompass all others,

• Giving all rectangles different $x$- and $y$- coordinates for all their edges.

In short, the grid of $(2n-1) \times (2n-1)$ sub-rectangles are all inside the big one.

The solution clearly generalizes to $d$ dimensions, achieving the trivial bound of $(2n-1)^d$.

---

The more interesting question is what numbers are possible? E.g. in the $n=5$ case, the above showed $(2n-1)^2 = 9^2 = 81$ is possible. I can also imagine $79$ in my head. But I havent found a way to get to exactly $80$ (and I think it may be impossible)...