# Maximum number of subrectangles that lie completely within a rectangle

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?

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)...

• oh whoops, your OP had $2(n-1)$ (probably a typo) and i blindly copied it! the relevant term should be $(2n -1)$, not $2(n-1)$. fixed now. May 11, 2020 at 4:10