Skip to main content
3 of 3
added 1437 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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.

enter image description here


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.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104