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?


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

| cite | improve this answer | |
  • $\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 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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