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.

enter image description here enter image description here

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.

enter image description here

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?


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

  • $\begingroup$ 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. $\endgroup$
    – antkam
    May 11, 2020 at 4:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .