I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally:Problem: Given N equal-sized squares and a rectangle with width W and height H, find out the maximum size of the squares L such that the squares fit inside the rectangle in such a way that their sides are orthogonal to the rectangle sides.So far, I think we have a O(sqrt(N)) solution, in which we assume W>H, start by trying to place all squares in a single row, then in two rows and so on, until we get to O(sqrt(N)). For formally, let nRows be a variable from 1 to sqrt(N), nCols = ceil(N/nRows) and then do L = min(H/nRows, W/nCols).I'm not completely sure the idea above is optimal. I was also wondering if we can solve this problem in O(1)?I've tried looking for orthogonal square packing, but the problem seems a bit different (or could we easily reduce on to another?)
Largest N squares that fit in a rectangle
optimization;computational geometry;packing;square grid