Breaking a rectangle into smaller rectangles with small diagonals

Question

Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of these rectangles $R_i$ as small as possible. I don't need a provably exact solution, just a heuristic that works well. Is there a common way that one does this? As an extreme example, if $a$ and $b$ happen to both be integers and $n$ happens to be equal to $ab$, then we can of course divide the rectangle into unit squares. Even if $n$ is not exactly equal to $ab$, we should be able to get a "good" division by stretching this grid slightly.

Answer 1

UPDATED

This is a very interesting question. Here is a motivating example followed by a conjectured solution.

Consider the problem of dividing the unit square into $28$ rectangles so as to minimize the maximum diagonal of any of the rectangles.

• Using $28$ rectangles of shape $\frac14 \times \frac17$ gives a diagonal of $\sqrt{\frac1{16}+\frac1{49}} \approx\sqrt{0.0829}$

• Using $25$ squares of side $\frac15$ then subdividing three to get $28$ rectangles gives maximum diagonal $\sqrt{\frac2{25}}=\sqrt{0.08}$

• Since $28=10+18,$ another option is the configuration below. It seems clear that it is optimal to have equal diagonals which gives the system of equations $$3u+2v=1 \text{ and }\frac1{36}+u^2=\frac1{25}+v^.2$$ Here the two equal sides of the second equation are the square of the diagonal. The solution turns out to be $u=\frac{45-13\sqrt{5}}{75} $ and $v=\frac{-20+13\sqrt{5}}{50}$ with diagonals $\sqrt{\frac{269-130\sqrt{5}}{500}}\approx \sqrt{0.0729}.$ I think, but do not claim, that this is optimal. I do think it can be shown to be optimal among solutions made up of rows running side to side.

---

The general problem is: given a rectangle of dimensions $a \times b$ (where we may assume $a \le b$) and an integer $n$, find a division of the rectangle into $n$ sub-rectangles in such a way as to minimize the longest diagonal of any sub-rectangle. I think that the optimal solution will have all diagonals equal. However let us specify that among solutions with the shortets longest diagonal, we prefer the one with diagonals as close to equal as possible, say ones which minimize $$\sum_{1 \le i_1 \lt i_2 \le n}(d_{i_1}-d_{i_2})^2$$ where $d_i$ is the diagonal of the $i$th sub-rectangle.

The idea (presented dynamically) is to start with a division of the rectangle into $j$ rows of $k$ rectangles, all of dimensions $\frac{a}{j} \times \frac{b}{k}$ where $j$ and $k$ are integers to be specified with $jk \ge n.$ Then remove $jk-n$ rectangles leaving either

• $j$ rows, $jk-n$ with $k-1$ rectangles and the rest with $k$ rectangles OR
• $k$ columns, $jk-n$ with $j-1$ rectangles and the rest with $j$ rectangles.

Let us assume it is the first case, the other being the same mutatis mutandis. Then we make all the rectangles in the deficient rows have width $\frac{b}{k-1}$ and then adjust the rows to have each of the two kinds of rectangles have equal diagonal. That is we use rectangles of sizes $u \times \frac{b}{k}$ and $v \times \frac{b}{k-1}$ where

• $u^2+(\frac{b}{k})^2=v^2+(\frac{b}{k-1})^2$
• $(j-(jk-n))u+(jk-n)v=a$.

It remains to specify $j$ and $k$. If the task was to find $n$ disjoint rectangles with total area $ab$ and minimize the maximum diagonal, then the solution would be $n$ squares of side $s=\sqrt{\frac{ab}{n}}$ and diagonal $\sqrt{\frac{2ab}{n}}.$ We can certainly not do better than that for the given problem and can only do that well exactly when $a$ and $b$ are both integer multiples of $s.$ To dispose of an extreme case which does not exactly fit the later description: if $a \lt s$ then use a single row of rectangles $a \times \frac{b}{n}.$ Otherwise, let $$j'=\Big\lfloor\frac{a}{s} \Big\rfloor \text{ and }k'=\Big\lfloor\frac{b}{s} \Big\rfloor.$$ Consider the choices $j=j'+1,k=k'$ and $j=j',k=k'+1$. If both satisfy $jk \ge n,$ then try both (I'll guess that the one minimizing $jk$ is better). If only one does, use it. Finally, if neither does, then use $j=j'+1,k=k'+1.$

This description has one try as many as $4$ cases. A certain amount of experimentation, which I have not done, might allow one to conjecture , and then possibly prove, rules for what choices to make for $j,k$ and which choice (rows or columns) to truncate. It would also provide a check if the description given works. For example I am implicitly assuming (in the first case) that $j \ge jk-n.$ If both this and $k \ge jk-n$ can fail at the same tie, then something is wrong with the description.

Answer 2

Without loss of generality you may assume that the horizontal spacing and vertical spacing are homogeneous. If the side of length $a$ is split into $n_1$ parts and the side of length $b$ is split into $n_2$ parts, a direct application of the arithmetic mean vs geometric mean shows that the subrectangle diagonal is maximised if $n_1 = \sqrt{\frac{an}b}$ and $n_2 = \sqrt{\frac{bn}{a}}$. Thus, you should try the two divisors of $n$ closest to the optimal value of $n_1$ and the one that gives you the smallest subrectangle diagonal is your optimal solution.

EDIT: You can try $n_1 = \left\lfloor \sqrt{\frac{an}b} \right\rfloor$ and $n_2 = \left\lfloor \sqrt{\frac{bn}{a}} \right\rfloor$ and then subdivide some of the small rectangles in order to have $n$. This would give an approximation that is not terrible.