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.
[Math] Breaking a rectangle into smaller rectangles with small diagonals
algorithmscomputational geometrydiscrete geometrymg.metric-geometry
Related Solutions
Golomb's book Polyominoes has a section on this. Call the smallest odd number of copies of a polyomino that can tile a rectangle its "odd-order". Then Golomb says there are polyominoes of odd order 1, 11, and 15+6t for all $t \ge 0$. The polyomino of odd order 11 is due to Klarner [1], and is illustrated here by Michael Reid.
Reid has lots of pictures of tilings of rectangles with polyominoes. In particular the 15+6t family can be seen: here are polyominoes with odd-order 15, odd-order 21, odd-order 27, and so on. Reid has shown [3] that other odd orders exist, including 35, 49, and 221, but I don't know if there's a general pattern.
Finally, Stewart and Wormstein [2] proved that polyominoes of order 3 do not exist. (Stewart's book Another Fine Math You've got Me Into suggests that Wormstein is a fictional character.)
[1] David A. Klarner, Packing a rectangle with congruent N-ominoes, J. Combin. Theory 7 (1969) 107-115,
[2] Stewart, Ian N. and Wormstein, Albert. Polyominoes of order 3 do not exist. J. Combin. Theory Series A 61 (1992) 130-136.
[3] Michael Reid. Tiling Rectangles and Half Strips with Congruent Polyominoes.
J. Combin. Theory Series A 80 (1997) 106-123.
Here is one relevant result, by Michael Hoffmann,
"Covering polygons with few rectangles," 2001. (PDF download link)
He shows that minimal covering by two or three congruent axis-aligned rectangles of a collection
of polygons with a total of $n$ vertices
can be found in $O(n)$ time.
He also says that the more general problem—covering a set of polygons by $p>3$ congruent rectangles—cannot be approximated by better than a factor of $2$ unless $P=NP$ (because of the relation to the $p$-center problem). He does not directly address covering just one polygon, or with covering by incongruent rectangles.
This latter problem (your problem) is partially addressed computationally in the paper 2011, "Covering a polygonal region by rectangles," Computational Optimization and Applications (Springer link). It appears that they start with a set of rectangles, and extend them until they form a cover.
Best Answer
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
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
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.