A geometry question that I feel utterly defeated by. I'm trying to design a responsive user interface that efficiently fits a variable number of square elements on a screen, by adjusting the size of the squares. With a known square size, the number of squares along and up will be implicit. I'm also very interested to know the answer.
I describe the problem as thus:
A known number of squares, n, must be fit as efficiently as possible (least remaining area) into a rectangle of known dimensions x & y. The dimension (equal width and height) of the squares, s, must be adjusted to achieve this. The squares must be axis-aligned. Find s.
All I've been able to establish is that where n/(w/h) is an integer, n + 1 is a worst case scenario of remainder. I can't seem to get any more facts to come out in the wash, but am interested in the working of the answer.
Update:
I've worked out (I hope), the maximum number of squares that may be fit, as follows:
max squares =
( floor( longest side / shortest side ) * divisor^2 ) +
( floor( r / ( shortest side / divisor ) ) * divisor )
Based on fitting squares with a size of the shortest side of the rectangle, dividing them down by the divisor (iteratively until enough squares are achieved), each time seeing how much of the remainder can be occupied by the divided down dimension.
Now I just need to turn this into a single formula so it doesn't have to be computed iteratively, if possible.
I'm decently sure this can be accomplished by simply adding the largest possible square i.e. has the minimum of width or height as side length. put square on side of rectangle and you end with a rectangle demension $x$ and $y-x$ without loss of generality. then simply repeat until either there's no remainder or your out of number of squares.