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:
-
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?
-
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?
Best Answer
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)...