Algorithm for maximizing coverage of rectangular area with scaling tiles

Question

I have N scalable square tiles (buttons) that need to be placed inside of fixed sized rectangular surface (toolbox). I would like to present the buttons all at the same size.

How could I solve for the optimal size of the tiles that would provide the largest area of the rectangular surface being covered by tiles.

Answer 1

Let W and H be the width and height of the rectangle.

Let s be the length of the side of a square.

Then the number of squares n(s) that you can fit into the rectangle is floor(W/s)*floor(H/s). You want to find the maximum value of s for which n(s) >= N

If you plot the number of squares against s you will get a piecewise constant function. The discontinuities are at the values W/i and H/j, where i and j run through the positive integers.

You want to find the smallest i for which n(W/i) >= N, and similarly the smallest j for which n(H/j) >= N. Call these smallest values i_min and j_min. Then the largest of W/i_min and H/j_min is the s that you want.

I.e. s_max = max(W/i_min,H/j_min)

To find i_min and j_min, just do a brute force search: for each, start from 1, test, and increment.

In the event that N is very large, it may be distasteful to search the i's and j's starting from 1 (although it is hard to imagine that there will be any noticeable difference in performance). In this case, we can estimate the starting values as follows. First, a ballpark estimate of the area of a tile is W*H/N, corresponding to a side of sqrt(W*H/N). If W/i <= sqrt(W*H/N), then i >= ceil(W*sqrt(N/(W*H))), similarly j >= ceil(H*sqrt(N/(W*H)))

So, rather than start the loops at i=1 and j=1, we can start them at i = ceil(sqrt(N*W/H)) and j = ceil(sqrt(N*H/W))). And OP suggests that round works better than ceil -- at worst an extra iteration.

Here's the algorithm spelled out in C++:

#include <math.h>
#include <algorithm>
// find optimal (largest) tile size for which
// at least N tiles fit in WxH rectangle
double optimal_size (double W, double H, int N)
{
    int i_min, j_min ; // minimum values for which you get at least N tiles 
    for (int i=round(sqrt(N*W/H)) ; ; i++) {
        if (i*floor(H*i/W) >= N) {
            i_min = i ;
            break ;
        }
    }
    for (int j=round(sqrt(N*H/W)) ; ; j++) {
        if (floor(W*j/H)*j >= N) {
            j_min = j ;
            break ;
        }
    }
    return std::max (W/i_min, H/j_min) ;
}

The above is written for clarity. The code can be tightened up considerably as follows:

double optimal_size (double W, double H, int N)
{
    int i,j ;
    for (i = round(sqrt(N*W/H)) ; i*floor(H*i/W) < N ; i++){}
    for (j = round(sqrt(N*H/W)) ; floor(W*j/H)*j < N ; j++){}
    return std::max (W/i, H/j) ;
}

Answer 2

I believe this can be solved as a constrained minimisation problem, which requires some basic calculus. .

Definitions:

a, l -> rectangle sides
   k -> number of squares
   s -> side of the squares

You have to minimise the function:

   f[s]:= a * l/s^2 - k

subject to the constraints:

  IntegerPart[a/s] IntegerPart[l/s] - k >= 0
  s > 0

I programed a little Mathematica function to do the trick

  f[a_, l_, k_] :=  NMinimize[{a l/s^2 - k , 
                               IntegerPart[a/s] IntegerPart[l/s] - k >= 0, 
                               s > 0}, 
                               {s}]     

Easy to read since the equations are the same as above.

Using this function I made up a table for allocating 6 squares

as far as I can see, the results are correct.

As I said, you may use a standard calculus package for your environment, or you may also develop your own minimisation algorithm and programs. Ring the bell if you decide for the last option and I'll provide a few good pointers.

HTH!

Edit

Just for fun I made a plot with the results.

And for 31 tiles:

Edit 2: Characteristic Parameters

The problem has three characteristic parameters:

1. The Resulting Size of the tiles
2. The Number of Tiles
3. The ratio l/a of the enclosing rectangle

Perhaps the last one may result somewhat surprising, but it is easy to understand: if you have a problem with a 7x5 rectangle and 6 tiles to place, looking in the above table, the size of the squares will be 2.33. Now, if you have a 70x50 rectangle, obviously the resulting tiles will be 23.33, scaling isometrically with the problem.

So, we can take those three parameters and construct a 3D plot of their relationship, and eventually match the curve with some function easier to calculate (using least squares for example or computing iso-value regions).

Anyway, the resulting scaled plot is: