4
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ The $O(\sqrt{N})$ algorithm sounds very clean and likely to be effective in practice. Is it really problematic in practice? How large is $N$ in practice? I can think of more efficient algorithms, but I suspect they might not matter in practice and might be an instance of premature optimization. Can you address my concerns? $\endgroup$ – D.W. Oct 8 '14 at 0:02
  • $\begingroup$ weird, can you prove that if $L_{max}$ does not use up either H or W, then you can always increase $L_{max}$ by a small amount and all squares still fit? $\endgroup$ – InformedA Oct 8 '14 at 3:12
  • $\begingroup$ Your initial sentence says "no rotations", but your "More formal" description doesn't include that restriction. Do the sides of the squares need to be parallel to the sides of the rectangle? $\hspace{1.78 in}$ $\endgroup$ – user12859 Oct 8 '14 at 3:40
  • $\begingroup$ Yeah, I forgot about it. Let me update $\endgroup$ – kunigami Oct 8 '14 at 13:16
1
$\begingroup$

Let

\begin{align} C&=\left\lfloor\frac WL\right\rfloor& R&=\left\lfloor\frac HL\right\rfloor \end{align}

be the maximum number of rows and columns respectively. It sounds as though you're looking for the maximum $L^*$ such that, when $L=L^*$, we have $CR\ge N$. Let

\begin{align} L_0&=\sqrt{\frac{WH}N}\\ C_0&=\left\lceil\frac W{L_0}\right\rceil=\left\lceil\sqrt{\frac{WN}H}\right\rceil& R_0&=\left\lceil\frac H{L_0}\right\rceil=\left\lceil\sqrt{\frac{HN}W}\right\rceil. \end{align}

Observe that $L\le\min{\{W/C_0,H/R_0\}}$ is sufficient, and $L\le L_0$ is necessary:

\begin{align} \frac{WH}{L^2}&\ge\left\lfloor\frac WL\right\rfloor\left\lfloor\frac HL\right\rfloor=CR\ge N\\ L&\le\sqrt{\frac{WH}N}=L_0, \end{align}

with equality only if $W/L_0$ and $H/L_0$ both are integers. As a result, the optimal solution has dimension either $C_0\times\lceil N/C_0\rceil$ or $\lceil N/R_0\rceil\times R_0$.

$\endgroup$
0
$\begingroup$

Another possible approach is to look for good rational approximations to the ratio $W/H$, i.e., positive integers $r,s$ such that $r/s \approx W/H$.

Any good solution to your problem immediately yields such a good rational approximation (just let $r = $ the number of rows of squares and $s = $ the number of columns). Similarly, any good rational approximation to $W/H$ suggests a candidate solution to your problem (let $k=\lceil \sqrt{N/rs} \rfloor$, and then consider an arrangement with about $kr$ rows and $ks$ columns). So, a plausible approach might be to generate a bunch of good rational approximations to $W/H$, then test each corresponding candidate layout to see which is the best.

There are various algorithms for generating good rational approximations to a desired number $\alpha \in \mathbb{R}$. For instance, you can use continued fractions to generate a set of candidate approximations; there is a mathematical guarantee that each candidate will be a very good approximation, in some well-defined mathematical sense. The running time to generate and examine all such continued fractions will be poly-logarithmic in $N$. However, I don't know whether this will be better in practice than your simple $O(\sqrt{N})$ time algorithm.

$\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.