Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

thank god there is a math section to this site, I'm going insane

I have a problem I know how to solve by trial and error but I'm trying to figure out the 'smart' way to do it so I can make it into a macro using autohotkey and never have to guess and check again.

I think what I need is an algorithm to do the following,

Here's the problem:

For any large rectangle, place the least amount of smaller rectangles inside the large rectangle with as equal spacing as possible, the smaller rectangles will all be A units wide and B units long.

Here's the parameters:

Smaller rectangles can only have a maximum area of 250 units. Smaller rectangle can't be more than 20 units in any direction. Smaller rectangle can't be less than 10 units in any direction. Smaller rectangles may overlap.

Here's how I manually solve it, takes a while and is messy:

I divide the big rectangle area by the smaller rectangle area. This gives me the minimum amount of rectangles possible, assuming no minimum or maximum sizing limitations. In some cases, the minimum or maximum sizing limitations of the smaller rectangles means I will have to use a few more rectangles. If I had a 5 unit by 200.01 unit big rectangle, for example, I would have to use 11 small rectangles to fill the big rectangle (the .01 makes me have to add another rectangle by itself), since I can't make the small rectangles longer than 20 units according to the parameters.

For most of these problems, the best way to figure out the best solution is to find the ratio of the sides of the big rectangle (a 200 by 400 rectangle would have a 1:2 ratio), and scale that down to the smaller rectangles. However, I have to be careful not to have a ratio that exceeds the size limits imposed on the smaller rectangles (10 minimum, 20 maximum).

Thanks for any help. It seems a lot simpler to me than how it looks on paper, but I still can't wrap my head around how to put it into an algorithm or solve it neatly in the quirky situations where you're not using nice clean numbers.

share|improve this question
    
I assume you want the smaller rectangles to fully cover the larger one? You may want to explicitly state that in the problem description. Also, does the solution really have to give the absolutely smallest number of rectangles, or is it OK if it sometimes uses, say, one rectangle more than would be theoretically necessary? And just what do you mean by "with as equal spacing as possible", and how important is that requirement? –  Ilmari Karonen Sep 15 '12 at 21:04
    
Ps. If it weren't for that maximum area limit, this would be trivial to solve. (Just tile enough 200 x 200 squares to cover the big rectangle, then make them overlap enough that they fit inside it.) –  Ilmari Karonen Sep 15 '12 at 21:09

2 Answers 2

up vote 1 down vote accepted

Here's a method that should give an optimal answer, assuming that all the small rectangles have the same shape and orientation. (I haven't ruled out the possibility that there could be arrangements of different-shaped rectangles that might be more efficient in some cases.)

First, assume that the smaller rectangles are all $x$ by $y$ units, where $12.5 \le x \le 20$ and $y = 250/x$. (There's no need to consider rectangles with $x \le 12.5$, since they can always be replaced by $12.5 \times 20$ rectangles with suitable overlap.) Then the number of such small rectangles required to cover the big $A$ by $B$ rectangle is $$f(x) = \lceil A/x \rceil \cdot \lceil B/y \rceil$$ where $\lceil a \rceil = \operatorname{ceil}(a)$ denotes the smallest integer greater than or equal to $a$.

We'll note that, as $x$ increases, $f(x)$ can only decrease at the points where $A/x$ is an integer. Thus, the minimum of $f(x)$ must be attained either at $x = 12.5$ or at $x = A/k$ for some integer $k$. To find the actual minimum, we can use the following procedure:

  • Let $x_0 = 12.5$ and let $n = \lceil A/x_0 \rceil$. Let $m = n - \lfloor A/20 \rfloor$.
  • Let $x_i = A/(n - i)$ for all $i$ from $1$ to $m$.
  • Find among the values $x_0$ to $x_m$ the one that gives the smallest $f(x)$.

Note that, in most cases, this procedure will yield a value of $x$ which exactly divides $A$, whereas in the other direction the small squares will cover up to $y \cdot \lceil B/y \rceil = 250/x \cdot \lceil xB/250 \rceil$ units. To get rid of the extra area, you can either reduce $y$ to $B / \lceil xB/250 \rceil$ (assuming that this does not reduce $y$ below the lower limit of $10$) or arrange for the rectangles to overlap.

Ps. If you want to make the small rectangles overlap approximately equally in both directions, you could replace the dimensions $x$ and $y = 250/x$ chosen by the above procedure with $y' = \frac12 y + \frac12 B / \lceil B/y \rceil$ (clipped to the range $12.5 \le y' \le 20$) and $x' = 250/y'$.


Here's the same algorithm in pseudocode. Assume that all variables and constants are floating point numbers; the function floor() rounds a number down and the function ceil() rounds it up to the next integer:

// Tile size constraints.  We only consider tiles with maximum area,
// since smaller tiles can be replaced by overlapping larger tiles:
const maxArea = 250;
const maxWidth = 20;
const minWidth = maxArea / maxWidth;

function coverRectangleWithTiles ( rectWidth, rectHeight ):
    // How many columns of tiles do we need at least?
    var minColumns = ceil( rectWidth / maxWidth );
    // ...and how many at most?
    var maxColumns = floor( rectWidth / minWidth );

    // First see what how well we can do with minimum-width tiles:
    var columns = maxColumns;
    var rows = ceil( rectHeight / maxWidth );
    // Lowest total found so far; we'll try to improve this below:
    var minTiles = columns * rows;

    // Now try it with wider tiles; we only need to try the minimum
    // tile width for each possible number of columns.  The case
    // columns = maxColumns is already tried above, so we can exclude
    // it (and should, because otherwise the formulas below might
    // give tileWidth < minWidth, and thus tileHeight > maxWidth):

    for columns from minColumns to maxColumns-1 do:
        // Find the minimum tile width for this number of columns:
        var tileWidth = rectWidth / columns;
        // ...the maximum height allowed for this width:
        var tileHeight = maxArea / tileWidth;
        // ...and the number of rows needed with this height:
        var rows = ceil( rectHeight / tileHeight );

        // Multiply columns with rows to get total number of tiles:
        var tiles = columns * rows;
        // ...and save it if it's smaller than the minimum so far:
        if tiles < minTiles then:
            minTiles = tiles;
            // Could also save the tile dimensions needed to obtain
            // the minimum here.
        end if
    end for

    return minTiles;
end function

Note that the algorithm above actually calculates the minimum number of non-overlapping tiles needed to cover a rectangle at least as large as the given one. That is to say, if the resulting number of tiles were arranged without overlap, they might (and usually would) extend outside the rectangle.

Normally, this shouldn't be a problem, since the tile dimensions can simply be reduced to make them fit exactly, and/or the tile positions can be adjusted to make them overlap instead of spilling outside the rectangle. However, when adjusting tile sizes, you'll have to keep in mind the hard lower width/height limit of 10 units, which the algorithm above ignores.

share|improve this answer
    
I've been reading over this for 4 days and still can't figure out, can you ultra pretty please put it into english for someone who doesn't speak advanced math? you lost me at weird a symbol = ceil, weird a symbol..is that symbol the same as big A, and what is the k you talk about later, what is n, what is i? what are the y' with the apostrophes. are you using some kind of software that can read those equations? –  Luke Allen Sep 20 '12 at 2:09
    
The "weird symbols" are just the usual math notation for the floor and ceiling function. So $\lfloor A/x \rfloor$ means "divide $A$ by $x$ and round upwards". The $x'$ and $y'$ are just variables; the $'$ is there to mark them as different from the original $x$ and $y$. (I could've just as well called them $x_2$ and $y_2$ or $x_{\rm new}$ and $y_{\rm new}$ or even $p$ and $q$.) –  Ilmari Karonen Sep 20 '12 at 13:41
    
$k$ is, as I write, "some integer"; the point is that when $x$ goes up, $f(x)$ can only go down at the points where $x$ evenly divides $A$. $n$ is, as I also write, defined to be equal to $\lceil A/x_0 \rceil$, i.e. $A$ divided by $x_0$, rounded up. Specifically, it's the minimum number of rectangles of width $x_0$ that we need to put side by side to cover a rectangular strip of width $A$. (BTW, I noticed that there was a sign error on those two lines; it's fixed now.) –  Ilmari Karonen Sep 20 '12 at 13:50
    
Ps. I take it that you have more of a programming than a math background? I can try to rewrite my answer to be "less mathy" later today or tomorrow, if that helps. –  Ilmari Karonen Sep 20 '12 at 13:53
    
it just seems to me that I would have to plug all that into something that would plot a graph with a bunch of answers, I don't see how to work out an actual answer for say 35x297 rectangle just using normal calculators? –  Luke Allen Sep 20 '12 at 16:53

The constraints on the small $x\times y$ rectangles are that $10=a\le x\le b=20$, $a\le y\le b$ and $xy\le c=250$. Observe that $ab\le c\le b^2$. The quality achieved by covering $A\times B$ with $n$ rectangles can be measured by the "loss" $n-\frac{AB}c$. A covering with loss $<1$ is clearly optimal.

The following method describes how to find a covering that is optimal in many cases and guaranteed to use at most two rectangles more than an optimal solution.

Let us see what $A\times B$ rectangles can be "losslessly" reduced to smaller rectangles.

Case 1: If $B\ge A\ge 33\frac13=\frac{bc}{b^2-c}$, then $\frac{b A}c- \frac Ab=A\cdot \frac{b^2-c}{bc}\ge1$, hence there exists an integer $n$ such that $$\tag1\frac {aA}c\le\frac Ab\le n\le \frac{b A}c\le\frac Aa,$$ where the outer inequalities follow from $ab\le c$. From $(1)$ we conclude $a\le\frac An\le b $ and $a\le \frac{nc}A\le b$. Therefore, $x:=\frac An$ and $y:=\frac {nc}A$ are valid side lengths for a small rectangle and because of $xy=c$, also the area constraint is obeyed. Therefore we can use $n$ rectangles $x\times y$ to reduce the $A\times B$ rectangle losslessly to a $A\times (B-y)$ rectangle. Note that $B-y\ge A-b$.

Case 1a: If $A\ge B\ge 33\frac13$, we may apply case 1 symmetrically, thus reducing $A\times B$ to $(A-y)\times B$ with $A-y\ge B-b$.

Case 2: If $33\frac13>A\ge\frac{2c}b=25$ and $B\ge \frac{2c}A$ (note that $ \frac{2c}A\le b$), then $\frac Ab<2$ and $\frac{bA}c\ge 2$. Hence $(2)$ holds woith the choice $n=2$ and we can continue as in case 1, thus reducing $A\times B$ losslessly to $A\times (B-y)$ with $B-y\ge 0$.

Case 2a: If $33\frac13> B\ge 25$ and $A\ge\frac{2c}B$, by symmetry with case 2, we can achieve losslessly a reduction of $A\times B$ to $(A-y)\times B$ with $A-y\ge 0$.

Case 3: If $b\ge A\ge \frac cb = 12\frac12$ and $B\ge \frac cA$, then $(2)$ holds with $n=1$, thus we can reduce $A\times B$ to $A\times (B-y)$ with $B-y\ge0$.

Case 3a: If $b\ge B\ge 12\frac12$ and $A\ge \frac cB$, by symmetry we reduce to $(A-y)\times B$ with $A\ge 0$.

If we start with $A\ge 25$ and $B\ge 25$ and apply the above cases repeatedly while applicable, we will achieve a lossless reduction until reaching a rectangle $A'\times B'$. Depending on what was the last case applied, we have

  • if it was case 1, $A'\ge 33\frac13$ and $B'\ge A'-b\ge 13\frac13$; moreover $B'<33\frac13$ as otherwise case 1 or 1a would apply; but then also $B'<25$ as otherwise case 2a would apply; moreover, $B'>20$ as otherwise case 3a would apply; we conclude $A'\le B'+b<45$. Since $B'>20$, we need at least two rectangles vertically; since $B'<25$ we may choose (allowing overlap) $y=12\frac12$ and $x=20$. If $33\frac13\le A'\le40$, this produces a covering with 4 rectangles and loss $<4-\frac{33\frac13\cdot20}{250}=1\frac13$, hence at most one rectangle from optimum. If $40<A'\le 45$, this produces 6 rectangles and loss $<6-\frac{40\cdot20}{250}=2\frac45$, hence at most two rectangles from optimum.
  • if it was case 1a, the situation is symmetric to above.
  • if it was case 2, $25\le A'<33\frac13$ and $B'\ge 0$; moreover $B'<\frac{2c}{A'}\le b$ as otherwise case 2 would apply; but then also $B'<12\frac12$ as otherwise case 3a would apply. If $B'=0$, we are done with no loss. Otherwise, we may choose $y=12\frac12>B'$ and $x=20$. If $A'\le 20$, this produces a covering by one rectangle with loss $<1$, hence optimal. If $A'>20$, we need two rectangles and the loss is $< 2$, that is possibly one from optimum (but optimum if $A'B'>c$).
  • if it was case 2a, the situation is symmetric to above.
  • if it was case 3, $20\ge A'\ge 12\frac12$ and $B'<\frac c{A'}\le 20$; if $B'=0$, we are done (without any loss); otherwise we can complete the task with a single $A'\times \frac c{A'}$ rectangle; the loss $1-\frac{A'B'}\c$ is less than $1$ and hence the covering is optimal.
  • if it was case 3a, the situation is symmetric to above.

In summary, the above method produces a covering that uses at most two rectangles more than an optimal covering as given by the area constraints. It does so for all $A\times B$ rectangles with $A\ge25$, $B\ge 25$. Personally I conjecture that even the coverings with loss $\ge1$ are truely optimal in many cases.

The method above neglects "long strips", i.e. where the shortest side is less than $25. For these, the "obvious" method should be optimal: If $A\le12\frac12$, stack $12\frac12\times 20$ rectangles. If $12\frac12

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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