3
$\begingroup$

I have a rectangle. This rectangle is divided into two columns; the widths of these columns are not necessarily equal, and are not known. I want to fill the rectangle with squares. The number of squares in each column is known. Each square should be the same size (congruent). I am trying to find the largest size that the squares can be so that they fill as much of the rectangle as possible, with all squares entirely contained inside the rectangle, arranged in a grid, and not overlapping. In this, I should find the best widths of each column for this number of squares.

This answer has a wonderful explanation of how to do this in one column. My question is how to do this in two.


An example

  • Rectangle is 9 by 14
  • Number of squares in column 1: 4
  • Number of squares in column 2: 7

Best arrangement of squares (where the dashed line is the divider between columns, and dotted lines represent boundaries between squares):

Squares


To summarize: Given the number of squares in each column and the size of the rectangle, how can I find the square size and the width of each column that minimize the unfilled area?

Thanks in advance!

$\endgroup$
0
$\begingroup$

Given data:

  • $H$ - height or rectangle
  • $W$ - width of rectangle
  • $N$ - number of squares in forst column
  • $M$ - number of squares in second column (without loosing generality we can say, that $M>N$)

Notice some facts:

  • If we fill first column in $k$ subcolumns, then we obtain $\left\lceil \frac{N}{k}\right\rceil$ subrows
  • If we fill first column in $l$ subrows, then we should fill the second in the same amount of subrows, and that means it will be filled with $\left\lceil \frac{M}{l}\right\rceil$ subcolumns
  • The above facts say, that filling first column with $k$ subcolumns will cause filling the second column with $\left\lceil \frac{M}{\left\lceil \frac{N}{k}\right\rceil}\right\rceil$ subcolumns and both columns are filled with $\left\lceil \frac{N}{k}\right\rceil$ subrows
  • If we fill first column with $k$ subcolumns, then height of the square is: $$a(k) = \min\left(\frac{H}{\left\lceil \frac{N}{k}\right\rceil}, \frac{W}{k+\left\lceil \frac{M}{\left\lceil \frac{N}{k}\right\rceil}\right\rceil}\right)$$

The maximal height of the square is then $$A=\max\limits_{k\in\{1,2,...,N\}} a(k)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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