Filling the grid

The long journey

A container of fixed width and height w,h∈R+w, h \in \R^+ is filled with n∈Nn \in \N (natural numbers without 00) squares positioned in a grid‑like fashion. The squares should cover as much of the w×hw \times h area as possible without overflowing, which means we must maximize the side length S∈R+S \in \R^+ of the square. In other words, we are searching a b×a∈N2b \times a \in \N^2 grid which fits all our nn squares and itself fits in the container while either being as wide or as tall as the container.

We can state the problem in a formal manner as follows:

Sola≔{ s∈R+:∃a,b∈N . n≤ab∧as=w∧bs≤h }Solb≔{ s∈R+:∃a,b∈N . n≤ab∧bs=h∧as≤w }Sol≔Sola∪SolbS≔max⁡Sol\brk[0]{\begin{gather*}} \brk{\begin{align*}} \text{Sol}_{a} \coloneqq \brk{\>&}\big\{\> s \in \R^{+} : \exists a, b \in \N \text{ . } \brk \brk{&\hspace{0.75em}}n \leq ab \land as = w \land bs \leq h \>\big\} \\ \text{Sol}_{b} \coloneqq \brk{\>&}\big\{\> s \in \R^{+} : \exists a, b \in \N \text{ . } \brk \brk{&\hspace{0.75em}}n \leq ab \land bs = h \land as \leq w \>\big\} \\ \text{Sol} \coloneqq \brk{\>&}\text{Sol}_{a} \cup \text{Sol}_{b} \\ S \coloneqq \brk{\>&}\max \text{Sol} \brk[0]{\end{gather*}} \brk{\end{align*}}

Let’s start solving for a solution sa∈Sols_a \in \rm Sol by attempting to find a grid as wide as the container. For any s∈Solas \in \text{Sol}_{a}:

n≤ab∧as=w∧bs≤h  ⟹  n≤wsb∧bs≤h  ⟹  n≤ws⋅hs  ⟹  n≤whs2  ⟹  s≤whn\begin{align*}\brk{&\enspace}n \leq ab \land as = w \land bs \leq h \brk &\implies n \leq \frac{w}{s}b \land bs \leq h \\ &\implies n \leq \frac{w}{s} \cdot \frac{h}{s} \\ &\implies n \leq \frac{wh}{s^2} \\ &\implies s \leq \sqrt{\frac{wh}{n}} \tag{1} \end{align*}

This is an upper bound on the side length. Let’s determine the grid’s number of columns, aa:

as=w  ⟹  a=ws  ⟹  (1)a≥wwhn  ⟹  a≥whn(s maximized∧a∈N)  ⟹  a=⌈whn⌉\begin{align*} as = w \implies &a = \frac{w}{s} \\ \overset{(1)}{\implies} &a \geq \frac{w}{\sqrt{\frac{wh}{n}}} \\ \implies &a \geq \sqrt{\frac{w}{h}n} \\ \brk[0]{(s \text{ maximized} \land a \in \N) \implies} \brk[1,]{\overset{s \text{ max.} \, \land \> a \in \N}{\implies} \>} &a = \left\lceil\sqrt{\frac{w}{h}n}\right\rceil \tag{2} \end{align*}

To further clarify the last step: since ss is in the denominator, maximizing it means aa must take the smallest value greater than or equal to RHS. Since a∈Na \in \N this is precisely RHS rounded up.

Knowing aa we can now determine the side length ss:

as=w  ⟹  s=wa\begin{equation} as = w \implies s = \frac{w}{a} \tag{3} \end{equation}

Since the implications in (1)(1) go in one direction only, we must check that s∈Sols \in \text{Sol}. The first necessary condition is:

n≤⌊ws⌋⋅⌊hs⌋\begin{equation} n \leq \left\lfloor \frac{w}{s} \right\rfloor \cdotp \left\lfloor \frac{h}{s} \right\rfloor \tag{4}\end{equation}

since a=⌊w/s⌋a = \left\lfloor w/s \right\rfloor and b=⌊h/s⌋b = \left\lfloor h/s \right\rfloor provide the number of squares the grid should have on each dimension, if it fits the squares and doesn’t overflow. Moreover, as=w  ⟹  a=w/s=⌊w/s⌋as = w \implies a = w/s = \left\lfloor w/s \right\rfloor, since a∈Na \in \N.

Let’s go to our initial assumptions.

n≤ab∧bs≤h  ⟹  n≤ahs  ⟹  n≤a⌊hs⌋⏟(i)∨(n>a⌊hs⌋∧n≤ahs)⏟(ii)\begin{equation} \tag{5} \begin{split} \brk[1,]{&}n \leq ab \land bs \leq h \brk[2,] \implies \brk[2,]{&}n \leq a \frac{h}{s} \brk[1] \brk[1]{&}\implies \underbrace{n \leq a \left\lfloor \frac{h}{s} \right\rfloor}_{\text{(i)}} \brk[2,] \brk[2,]{&\negthickspace}\lor \underbrace{\left(n > a \left\lfloor \frac{h}{s} \right\rfloor \land n \leq a \frac{h}{s}\right)}_{\text{(ii)}} \end{split} \end{equation}

In case (i)\text{(i)} we can take b=⌊h/s⌋b = \left\lfloor h/s \right\rfloor, which means bs≤hbs \le h. Thus, ss as determined above is in Sola⊆Sol\text{Sol}_{a} \sube \text{Sol}. But in case (ii)\text{(ii)}, b=⌊h/s⌋  ⟹  n>ab  ⟹  s∉Solb = \left\lfloor h/s \right\rfloor \implies n > ab \implies s \notin \text{Sol}. A new solution s′s' must be found.

Let’s analyze what follows from (ii)\text{(ii)}:

a⌊hs⌋<n≤ahs  ⟹  ⌊hs⌋<hs∧n≤ahs  ⟹  hs<⌈hs⌉∧n≤ahs  ⟹  n<a⌈hs⌉\begin{align*} \brk{&}a \left\lfloor \frac{h}{s} \right\rfloor < n \leq a \frac{h}{s} \brk \implies &\left\lfloor \frac{h}{s} \right\rfloor < \frac{h}{s} \land n \leq a \frac{h}{s} \\ \implies &\frac{h}{s} < \left\lceil \frac{h}{s} \right\rceil \land n \leq a \frac{h}{s} \\ \implies &n < a \left\lceil \frac{h}{s} \right\rceil \tag{6} \end{align*}

This means b=⌈h/s⌉b = \left\lceil h/s \right\rceil is a safe choice for the aa that we’ve determined, and a candidate for s′s' is:

s′=hb=h⌈hs⌉=(3)h⌈hwa⌉\begin{equation} s' = \frac{h}{b} = \frac{h}{\left\lceil \frac{h}{s} \right\rceil} \overset{(3)}{=} \frac{h}{\left\lceil \frac{h}{w}a \right\rceil} \tag{7}\end{equation}

Is this s′∈Sols' \in \text{Sol}? Yes, in fact in Solb\text{Sol}_{b}: (6)  ⟹  n≤ab(6) \implies n \leq ab, (7)  ⟹  bs′=h(7) \implies bs' = h and

as′=ah⌈hwa⌉=ah⌈ahw⌉  ⟹  ⌈x⌉≥xas′≤ahahw  ⟹  as′≤w\begin{equation} \tag{8} \begin{split} \brk{&}as' = \frac{ah}{\left\lceil \frac{h}{w}a \right\rceil} = \frac{ah}{\left\lceil \frac{ah}{w} \right\rceil} \brk \overset{\left\lceil x \right\rceil \geq x}{\implies} \brk{&}as' \leq \frac{ah}{\frac{ah}{w}} \implies as' \leq w \end{split} \end{equation}

With that we have determined sas_a. Here’s its formula based only on inputs w,h,nw, h, n:

a=⌈whn⌉sa={waif n≤a⌊hwa⌋h⌈hwa⌉else\begin{align*} a \brk{&}= \left\lceil\sqrt{\frac{w}{h}n}\right\rceil \qquad \brk s_a \brk{&}= \begin{cases} \frac{w}{a} &\text{if } n \leq a \left\lfloor \frac{h}{w}a \right\rfloor \\ \frac{h}{\left\lceil \frac{h}{w}a \right\rceil} &\text{else} \end{cases} \end{align*}

Analogously goes the process for determining sbs_b, whose formula is:

b=⌈hwn⌉sb={hbif n≤b⌊whb⌋w⌈whb⌉else\begin{align*} b \brk{&}= \left\lceil\sqrt{\frac{h}{w}n}\right\rceil \qquad \brk s_b \brk{&}= \begin{cases} \frac{h}{b} &\text{if } n \leq b \left\lfloor \frac{w}{h}b \right\rfloor \\ \frac{w}{\left\lceil \frac{w}{h}b \right\rceil} &\text{else} \end{cases} \end{align*}

Finally, S=max⁡{ sa,sb }S = \max \Set{s_a, s_b}.

Sadly, this algorithm sometimes fails to find the optimal solution. For example, inputs:

What do these inputs have in common? When does this algorithm have issues?

To investigate this, let’s simplify our solution statement. Observe that:

sw∈Sola  ⟺  asw=w∧bsw≤h  ⟺  a≥rb∧sw=wawsh∈Solb  ⟺  bsh=h∧ash≤w  ⟺  rb≥a∧sh=hbhwith n≤ab for all of the above\begin{equation} \tag{9} \begin{split} s_w \in \text{Sol}_a \iff &as_w = w \land bs_w \le h \brk \iff \brk{&}a \ge rb \land s_w = \frac{w}{a_w} \\ s_h \in \text{Sol}_b \iff &bs_h = h \land as_h \le w \brk \iff \brk{&}rb \ge a \land s_h = \frac{h}{b_h} \\ \brk[0]{&}\text{with } n \le \brk{\thickspace&}ab \brk{\text{ for all}}\brk[0]{\text{ for all of the above}} \end{split} \end{equation}

We’ve simplified width and height to just their ratio, r=whr = \frac{w}{h}. Moreover, we don’t need the side lengths themselves to compare them. Let sw=waws_w = \frac{w}{a_w}, sh=hbhs_h = \frac{h}{b_h}. Then:

sw>sh  ⟺  waw>hbh  ⟺  1aw>1rbh  ⟺  aw<rbh\begin{equation} \tag{10} \begin{split} s_w > s_h \iff \brk[2,]{&}\frac{w}{a_w} > \frac{h}{b_h} \brk[2,] \iff \brk{&}\frac{1}{a_w} > \frac{1}{rb_h} \brk \iff \brk{&}a_w < rb_h \end{split} \end{equation}

We can now state the final solution:

aw=min⁡{ a∈N:∃bw . a≥nbw∧a≥rbw }bh=min⁡{ b∈N:∃ah . b≥nah∧b≥ahr }s={sw=waw if aw<rbh,sh=hbh otherwise\begin{equation} \begin{split} a_w &= \min \Set{a \in \N : \exist b_w \text{ . } a \ge \frac{n}{b_w} \land a \ge rb_w} \\ b_h &= \min \Set{b \in \N : \exist a_h \text{ . } b \ge \frac{n}{a_h} \land b \ge \frac{a_h}{r}} \\ s &= \begin{cases} s_w = \frac{w}{a_w} &\text{ if } a_w < rb_h, \\ s_h = \frac{h}{b_h} &\text{ otherwise} \end{cases} \end{split}\tag{11} \end{equation}

The problem is reduced to just a,ba, b and rr. This simplification unlocks a powerful geometric representation in the 2D plane: we’re looking for points (aw,bw),(ah,bh)∈N2(a_w, b_w), (a_h, b_h) \in \N^2 such that they’re on or above the hyperbola xy=nxy = n while accounting for their position relative to the line x=ryx = ry. x=ax = a is used as stand‑in for columns in the continuous space, y=by = b for rows. Take a look (graph A; full visualizer here):

An introductory graph

This is the graph for the n=8,w=10,h=2n = 8, w = 10, h = 2 example above, with r=10/2=5r = 10/2 = 5. The black area under y=rxy = rx contains all fit‑width solutions, the red area all the fit‑height solutions. The union of these two contains the entire solution space, all (a,b)(a, b) for which n≤abn \le ab, i.e. all grid dimensions which fit all squares. Points on the green‑red line x=ryx = ry are grid dimensions having the ratio exactly rr. Black points are a subset of other solution candidates.

The symmetry of the problem with respect to ratio can now be directly visualized. For n=13n = 13 and r=3r = 3, respectively r=1/3r = 1/3, we have:

r > 1 graph to depict symmetry of problem” width=“300” height=“300” /> <img loading=lazy src=

Terminology‑wise, from here on (aw,bw),(ah,bh)(a_w, b_w), (a_h, b_h) will be called a fit‑width point, respectively a fit‑height point, if the points respect the requirements in (9)\text{(9)}; if the points are those described in (11)\text{(11)}, they’ll also be called minimal points (minimized coordinates for maximal side‑length). sws_w and shs_h will be called fit‑width and fit‑height solutions; unless explicitly mentioned, the (aw,bw),(ah,bh)(a_w, b_w), (a_h, b_h) points implied by sws_w and shs_h are not necessarily minimal. Sometimes only awa_w or bhb_h will be mentioned but keep in mind that by definition they do have a pair bwb_w and aha_h.

Let’s now analyze the solution space.

First, notice the purple point at the intersection of the hyperbola and the line – that is, the (x0,y0)(x_0, y_0) where ny0=ry0\frac{n}{y_0} = ry_0 – is special. This would be the “ideal” point, if rows and columns could be fractional somehow: only these dimensions exactly fit all squares and have the exact desired ratio. Notice that:

x0=ny0=ry0  ⟺  x0=rn∧y0=nr\begin{equation} \begin{split} \brk{&}x_0 = \frac{n}{y_0} = ry_0 \brk \iff \brk{&}x_0 = \sqrt{rn} \land y_0 = \sqrt{\frac{n}{r}} \tag{12} \end{split} \end{equation}

The number of columns aa chosen in (2)\text{(2)} is precisely ⌈x0⌉\left\lceil x_0 \right\rceil. This is the visual confirmation of that result: all the fit‑width points will find themselves to the left of that point, all the fit‑height points to its right. In other words:

∀aw,bh . aw≥x0∧bh≥y0\begin{equation} \forall a_w, b_h\text{ . } a_w \ge x_0 \land b_h \ge y_0 \tag{13} \end{equation}

If parameters are “nice” such that x0,y0∈Nx_0, y_0 \in \N the minimal fit‑width and fit‑height points coincide (graph B):

Parameters where the fit-width and fit-height solutions coincide

Second, when is a point valid, i.e. satisfies solution requirements in (9)\text{(9)}? Also, can multiple points give the same solution? Consider the following (n=23,r=3.9n = 23, r = 3.9, graph C):

The 4 points next to (ah,bh)(a_h, b_h) have the same ordinate and the point above (aw,bw)(a_w, b_w) the same abscissa, therefore their corresponding side lengths are still shs_h, respectively sws_w. This follows directly from the solution requirements in (9)\text{(9)}:

Fit width:awbw≥n∧aw≥rbw  ⟺  naw≤bw≤awr  ⟺  ⌈naw⌉≤bw≤⌊awr⌋Fit height:ahbh≥n∧bh≥ahr  ⟺  ⌈nbh⌉≤ah≤⌊rbh⌋\begin{equation} \hspace{-1em}\begin{split} \brk[0]{\begin{aligned}} \brk{\begin{gathered}} \text{Fit width:} \\ a_wb_w \ge n \land a_w \ge rb_w \brk \iff \brk[0]{&}\frac{n}{a_w} \le b_w \le \frac{a_w}{r} \\ \iff \brk[0]{&}\left\lceil \frac{n}{a_w} \right\rceil \le b_w \le \left\lfloor \frac{a_w}{r} \right\rfloor \brk[0]{\\} \brk{\\[1em]} \text{Fit height:} \\ a_hb_h \ge n \land b_h \ge \frac{a_h}{r} \brk \iff \brk[0]{&}\left\lceil \frac{n}{b_h} \right\rceil \le a_h \le \left\lfloor rb_h \right\rfloor \brk[0]{\end{aligned}} \brk{\end{gathered}} \end{split} \tag{14} \end{equation}

We can add the ceiling and floor as a consequence of them being residuated mappings. Notice how the intervals describe the space between the hyperbola and the line for aha_h and bwb_w. Doesn’t matter which value from these intervals aha_h and bwb_w have, the solutions of (aw,bw)(a_w, b_w), (ah,bh)(a_h, b_h) are the same. The ceilings and floors are visible in the graph too: the points are a bit above/under the function graphs too. We can compress the inequality to get the validity condition:

aw valid   ⟺  ⌈naw⌉≤⌊awr⌋bh valid   ⟺  ⌈nbh⌉≤⌊rbh⌋\begin{equation} \begin{split} a_w \text{ valid }\iff &\left\lceil \frac{n}{a_w} \right\rceil \le \left\lfloor \frac{a_w}{r} \right\rfloor \\ b_h \text{ valid }\iff &\left\lceil \frac{n}{b_h} \right\rceil \le \left\lfloor rb_h \right\rfloor \end{split} \tag{15} \end{equation}

The number of points with equal solutions is easily derived by subtracting the interval endpoints.

Third, which points give the optimal solution ss? How do they compare? Recall (10)\text{(10)}:

sw>sh  ⟺  aw<rbh\begin{align*} s_w > s_h \iff a_w < rb_h \end{align*}

From (9)\text{(9)} we know that for any (ah,bh)(a_h, b_h) fit‑height point, ah≤rbha_h \le rb_h, meaning rbhrb_h is an upper bound on a fit‑height solution’s number of columns. Therefore:

A fit‑width point with less columns than some fit‑height point gives the better solution between the two.

If rbh∉Nrb_h \notin \N then both aw≤⌊rbh⌋a_w \le \lfloor rb_h \rfloor and ah≤⌊rbh⌋a_h \le \lfloor rb_h \rfloor, meaning they can have at most as many columns. This is unsurprising: the fit‑width solution stretches the columns fully, while the fit‑height doesn’t.

What about the number of rows? Since aw≥rbwa_w \ge rb_w we get that:

aw≥rbw∧sw>sh  ⟹  rbw≤a<rbh  ⟹  bw<bh\begin{equation} \begin{split} \brk[2,]{&}a_w \ge rb_w \land s_w > s_h \brk[2,] \implies \brk{&}rb_w \le a < rb_h \brk \implies \brk{&}b_w < b_h \tag{16} \end{split} \end{equation}

This means:

A fit‑width point must have less rows than a fit‑height point to correspond to a better solution.

It makes sense intuitively: a fit‑height solution stretches the rows fully, a fit‑width doesn’t; if a fit‑width solution has as many rows or more, it must be worse.

We can observe these properties on the graphs above:

Graph C shows that having less rows doesn’t matter, since one can simply add more rows. Mathematically, for (aw,bw)(a_w, b_w) fit‑width, (ah,bh)(a_h, b_h) fit‑height points, if sw≤shs_w \le s_h:

aw≥rbh≥ah∧n≤ahbh  ⟹  aw≥rbh∧n≤awbh  ⟹  (9)(aw,bh) fit-width\begin{align*} \brk[2,]{&}a_w \ge rb_h \ge a_h \land n \le a_hb_h \brk[2,] \implies \brk{&}a_w \ge rb_h \land n \le a_wb_h \brk \overset{\text{(9)}}{\implies} \brk{&}(a_w, b_h) \text{ fit-width} \end{align*}

Note that all the results above apply for any rr.

Fourth and finally, when r≥1r \ge 1 if the minimal fit‑width solution is strictly better than any fit‑height solution, then it corresponds uniquely to a single point (prove it yourself! or see appendix for proof). Symmetrically for r<1r < 1 the same applies for the fit‑height solution.

We can now analyze when the algorithm we’ve developed fails. Translating its solution to points:

Pa={(aw=⌈rn⌉,bw=⌊awr⌋)0if n≤awbw(ah=aw,bh=⌈awr⌉)1elsePb={(ah=⌊rbh⌋,bh=⌈nr⌉)0if n≤ahbh(aw=⌈rbw⌉,bw=bh)1else\begin{align*} P_a &= \begin{cases} (a_w = \left\lceil \sqrt{rn} \right\rceil, b_w = \left\lfloor{\frac{a_w}{r}}\right\rfloor)_{0} &\text{if } n \le a_wb_w \\ (a_h = a_w, b_h = \left\lceil \frac{a_w}{r} \right\rceil)_{1} &\text{else} \end{cases} \\ P_b &= \begin{cases} (a_h = \left\lfloor{rb_h}\right\rfloor, b_h = \left\lceil \sqrt{\frac{n}{r}} \right\rceil)_{0} &\text{if } n \le a_hb_h \\ (a_w = \left\lceil rb_w \right\rceil, b_w = b_h)_{1} &\text{else} \end{cases} \\ \end{align*}

Recall that if a fit‑width point has a solution greater than that of a fit‑height point it will have less rows. Above we can see that all of Pa,1,Pb,0,Pb,1P_{a,1}, P_{b,0}, P_{b,1} have a number of rows greater than y0y_0: for PbP_b it is by construction, and for Pa,1P_{a,1}:

⌈awr⌉=⌈⌈rn⌉r⌉≥⌈rn⌉r≥nr=y0\left\lceil \frac{a_w}{r} \right\rceil = \left\lceil \frac{\left\lceil \sqrt{rn} \right\rceil}{r} \right\rceil \ge \frac{\left\lceil \sqrt{rn} \right\rceil}{r} \ge {\sqrt{\frac{n}{r}} = y_0}

Moreover, for r≥1r \ge 1 there exists a fit‑height solution with bh=⌈y0⌉b_h = \left\lceil y_0 \right\rceil with very high probability and fit‑width solutions with aw=⌈x0⌉a_w = \left\lceil x_0 \right\rceil are highly unlikely – in fact, almost never likely for r≥2r \ge 2 (see appendix for proof). Therefore, the optimal solution mainly corresponds to a unique fit‑width point (aw,bw)(a_w, b_w) with aw>⌈x0⌉a_w > \lceil x_0 \rceil and bw<⌈y0⌉b_w < \lceil y_0 \rceil yet the algorithm is optimized to find a fit‑height point (ah,bh)(a_h, b_h) with ah≤⌈x0⌉a_h \le \lceil x_0 \rceil and bh≥⌈y0⌉b_h \ge \lceil y_0 \rceil. By the conclusions in the appendix, the outcome is predominantly ratio‑dependent; for the vast majority of ratios the algorithm does not find the optimal solution (e.g. r∈[1.5,2)r \in [1.5, 2) paired with most nn).

Let’s visualize this on the graphs of the two counterexamples given above (r=5,n=8r = 5, n = 8 and r=3.5,n=20r = 3.5, n = 20):

The initial fit‑width point candidate Pa,0P_{a,0} is invalid in both cases (under the hyperbola), so the algorithm falls back to Pa,1P_{a,1}, a fit‑height point. In the first example, Pb,0P_{b,0} is already valid, so the fallback Pb,1P_{b,1} is not used; in the second, the fallback is used instead but even though it’s a fit‑width point its solution is equivalent to the fit‑height solution, as they have the same number of rows.

Let’s now build a new algorithm. This algorithm should find the minimal fit‑width and fit height points and pick the solution with the greater side length. Using (15)\text{(15)} , the solution we’re looking for is:

aw=min⁡{ a∈N:⌈na⌉≤⌊ar⌋ }bh=min⁡{ b∈N:⌈nb⌉≤⌊rb⌋ }s=max⁡{ waw,hbh }\begin{gather*} a_w = \min \Set{a \in \N : \left\lceil \frac{n}{a} \right\rceil \le \left\lfloor{\frac{a}{r}}\right\rfloor} \\ b_h = \min \Set{b \in \N : \left\lceil \frac{n}{b} \right\rceil \le \left\lfloor{rb}\right\rfloor} \\ s = \max \Set{ \frac{w}{a_w}, \frac{h}{b_h} } \end{gather*}

Let’s walk through how we translate this to code. First, we are looking for minimum awa_w and bhb_h; from (13)\text{(13)} we know that aw≥⌈rn⌉a_w \ge \left\lceil \sqrt{rn} \right\rceil and b≥⌈nr⌉b \ge \left\lceil \frac{n}{r} \right\rceil. We’ll initialize variables a and b to those values. Then we need to ensure the validity condition; for that, we just increment a and b in a loop until the condition holds. The loops execute while awa_w and bhb_h are invalid points:

⌈na⌉>⌊ar⌋  ⟺  a<r⌈na⌉⌈nb⌉>⌊rb⌋  ⟺  rb<⌈nb⌉\begin{equation} \begin{split} &\left\lceil\frac{n}{a}\right\rceil > \left\lfloor{\frac{a}{r}}\right\rfloor \iff a < r\left\lceil\frac{n}{a}\right\rceil \\ &\left\lceil\frac{n}{b}\right\rceil > \left\lfloor{rb}\right\rfloor \iff rb < \left\lceil\frac{n}{b}\right\rceil \end{split} \tag{17} \end{equation}

The implementation follows directly:

const r = w / h;

let a = Math.ceil(Math.sqrt(r * n));
for (; a < r * Math.ceil(n / a); a++);

let b = Math.ceil(Math.sqrt(n / r));
for (; r * b < Math.ceil(n / b); b++);

return Math.max(w / a, h / b);

The algorithm always terminates: as aa grows, ⌈na⌉\left\lceil\frac{n}{a}\right\rceil decreases and ⌈ar⌉\left\lceil\frac{a}{r}\right\rceil increases, shrinking the interval until the ordering of its endpoints is swapped; likewise for bb. The values at the end of each loop are minimal – we check every value one by one in ascending order.

Intuitively, if the loop condition holds there is no valid (aw,bw)(a_w, b_w) or (ah,bh)(a_h, b_h) fit‑width, respectively fit‑height point with the iteration’s current awa_w or bhb_h value. If we take bw=⌈na⌉b_w = \left\lceil\frac{n}{a}\right\rceil and ah=⌈nb⌉a_h = \left\lceil\frac{n}{b}\right\rceil (the minimum values for a valid solution) we can imagine this algorithm as “walking away” from (x0,y0)(x_0, y_0) alongside the hyperbola until we (inevitably) find ourselves in the fit‑width/fit‑height solution spaces:

a0a_0 and b0b_0 are the starting points, right next to (x0,y0)(x_0, y_0). The algorithm “walks down” to (aw,bw)(a_w, b_w) and “up” to (ah,bh)(a_h, b_h). In fact, in this example, b0b_0 is initialized directly to (ah,bh)(a_h, b_h); a0a_0 must be incremented once.

We have convinced ourselves of correctness. To analyze its runtime complexity, let’s denote a0=⌈rn⌉a_0 = \left\lceil\sqrt{rn}\right\rceil the starting value of aa. Since the loop condition is a<r⌈na⌉a < r\left\lceil{\frac{n}{a}}\right\rceil, aa will be incremented at most ⌈r⌈na⌉−a0⌉\left\lceil{r\left\lceil{\frac{n}{a}}\right\rceil - a_0}\right\rceil times. Since aa increases ⌈na⌉≤⌈na0⌉\left\lceil{\frac{n}{a}}\right\rceil \le \left\lceil{\frac{n}{a_0}}\right\rceil. We can now count iterations:

⌈r⌈na⌉−a0⌉<r⌈na0⌉−a0+1<rna0+r−a0+1=rn⌈rn⌉+r−⌈rn⌉+1<rnrn+r−rn+1=r+1\begin{equation} \begin{split} \brk{&}\left\lceil{r\left\lceil{\frac{n}{a}}\right\rceil - a_0}\right\rceil \brk &< r \left\lceil{\frac{n}{a_0}}\right\rceil - a_0 + 1 \\ &< r \frac{n}{a_0} + r -a_0 + 1 \\ &= r\frac{n}{\left\lceil \sqrt{rn} \right\rceil} + r - \left\lceil\sqrt{rn}\right\rceil + 1 \\ &< \frac{rn}{\sqrt{rn}} + r - \sqrt{rn} + 1 \\ &= r + 1 \end{split}\tag{18} \end{equation}

This means at most ⌊r⌋+1\left\lfloor r \right\rfloor + 1 iterations and a runtime of O(r)\mathcal{O}(r), dependent only on the aspect ratio of the grid. To show that the bound is tight, consider this following example:

Here n=33,r=8.3n = 33, r = 8.3. A very rare case when the fit‑height starting point b0b_0 is in the fit‑width solution space. Consider the iteration count of the fit‑height loop of the algorithm – by the same reasoning it is ⌊1r⌋+1\left\lfloor{\frac{1}{r}}\right\rfloor + 1. It’s visible that in this example the loop will do exactly 1 iteration to reach (ah,bh)(a_h, b_h). Since the algorithm is symmetric this proves tightness for the first loop by using the same nn and r′=1rr' = \frac{1}{r}.

With a correct algorithm and good understanding of why it works, we conclude here.

Appendix

Uniqueness of fit‑width solution when r≥1r \ge 1

Let (a,b)(a, b) be a minimal fit‑width point. We prove there is no b′b' such that (a,b′)(a, b') is a fit‑width point when r≥1r \ge 1 and (a,b)(a, b) corresponds to the best solution, meaning that sw>shs_w > s_h for all (ah,bh)(a_h, b_h) fit‑height points.

Assume towards a contradiction there exists b′≠bb' \ne b such that (a,b′)(a, b') is a fit‑width point. Without loss of generality, we can further assume b<b′b < b'. From (14)\text{(14)} and the minimality of aa we can write aa in terms of b′b':

n≤ab′∧a≥rb′  ⟹  a≥⌈nb′⌉∧a≥⌈rb′⌉  ⟹  a=max⁡{ ⌈nb′⌉,⌈rb′⌉ }n \le ab' \land a \ge rb' \implies a \ge \left\lceil \frac{n}{b'} \right\rceil \land {a \ge \left\lceil rb' \right\rceil} \implies a = \max \Set{ \left\lceil \frac{n}{b'} \right\rceil, \left\lceil rb' \right\rceil }

Suppose that a=⌈nb′⌉a = \left\lceil \frac{n}{b'} \right\rceil. Since we have n≤abn \le ab from (14)\text{(14)}, b<b′b < b' and r≥1r \ge 1:

a−1<nb′  ⟹  b′(a−1)<ab  ⟹  (b′−b)a<b′  ⟹  a<rb′{a - 1 < \frac{n}{b'}} \implies {b'(a - 1) < ab} \implies {(b' - b)a < b'} \implies a < rb'

But a≥rb′a \ge rb' so we’ve reached a contradiction. Therefore, together with the first result:

a≠⌈nb′⌉  ⟹  ⌈nb′⌉<⌈rb′⌉=a  ⟹  ⌈nb′⌉≤⌊rb′⌋{a \ne \left\lceil \frac{n}{b'} \right\rceil} \implies {\left\lceil \frac{n}{b'} \right\rceil < \left\lceil rb' \right\rceil = a} \implies {\left\lceil \frac{n}{b'} \right\rceil \le \left\lfloor rb' \right\rfloor}

By (14)\text{(14)} this means for integer ⌈nb′⌉≤a′≤⌊rb′⌋\left\lceil \frac{n}{b'} \right\rceil \le a' \le \left\lfloor rb' \right\rfloor the point (a′,b′)(a', b') is fit‑height (real example in graph C). But then, since for this one fit‑height point sh=hb′s_h = \frac{h}{b'}:

a≥rb′  ⟹  sw≤sh{a \ge rb' \implies s_w \le s_h}

In conclusion, b′≠bb' \ne b contradicts sw>shs_w > s_h, thus b′b' can’t exist and (a,b)(a, b) is unique.

Position of solution points relative to (x0,y0)(x_0, y_0)

We’ll approach this subject by handling fit‑height points where r≥1r \ge 1. Due to the symmetry of the problem relative to ratio, we can make more general conclusions afterwards.

b=⌈y0⌉=⌈nr⌉b = \lceil y_0 \rceil = \left\lceil{\sqrt{\frac{n}{r}}}\right\rceil is a valid fit‑height point by (15)\text{(15)} if and only if:

⌈nb⌉≤⌊rb⌋\begin{align*} \left\lceil{\frac{n}{b}}\right\rceil \le \left\lfloor{rb}\right\rfloor \end{align*}

A sufficient condition is:

rb−nb≥1  ⟹  rb2−n−b≥0  ⟹  b≥12r+14r2+nr>nr\begin{align*} \brk{&}rb - \frac{n}{b} \ge 1 \brk \implies &rb^2 -n - b \ge 0 \\ \implies &b \ge \frac{1}{2r} + \sqrt{\frac{1}{4r^2} + \frac{n}{r}} > \sqrt{\frac{n}{r}} \end{align*}

If bb is greater than that the fit‑height point (a,b)(a, b) is valid. The condition excludes cases when ∃k∈N . k∈[nb,rb]\exist k \in \N \text{ . } k \in [\frac{n}{b}, rb] (e.g. when y0∈Ny_0 \in \N then the point valid for every nn) but it is easy to quantify. We can use it to answer: for fixed r≥1r \ge 1 what’s the probability for bb to be a valid fit‑height solution?

To do this, observe that by the properties of ceiling, nr≤b<nr+1\sqrt{\frac{n}{r}} \le b < \sqrt{\frac{n}{r}} + 1. We can bound the expression above likewise, using r≥1r \ge 1:

nr<12r+14r2+nr<12+(12+nr)2=nr+1\sqrt{\frac{n}{r}} < {\frac{1}{2r}+\sqrt{\frac{1}{4r^2}+\frac{n}{r}}} < {\frac{1}{2} + \sqrt{\left(\frac{1}{2} + \sqrt{\frac{n}{r}}\right)^2}} = {\sqrt{\frac{n}{r}} + 1}

It follows that:

nr<12r+14r2+nr≤b=⌈nr⌉<nr+1\sqrt{\frac{n}{r}} < {\frac{1}{2r} + \sqrt{\frac{1}{4r^2}+\frac{n}{r}}} \le {b = \left\lceil{\sqrt{\frac{n}{r}}}\right\rceil} < {\sqrt{\frac{n}{r}} + 1}

If we subtract nr\sqrt{\frac{n}{r}}, the difference will be always between 00 and 11:

0<12r+14r2+nr−nr⏟Br(n)≤⌈nr⌉−nr⏟Cr(n)<1{0 < \underbrace{\frac{1}{2r} + \sqrt{\frac{1}{4r^2}+\frac{n}{r}} - \sqrt{\frac{n}{r}}}_{B_r(n)}} \le {\underbrace{\left\lceil{\sqrt{\frac{n}{r}}}\right\rceil - \sqrt{\frac{n}{r}}}_{C_r(n)} < 1}

Let’s visualize this:

First graph depicts r=1r = 1, the second r=3r = 3. The red points represent Cr(n)C_r(n), the black points Br(n)B_r(n). Whenever a red point is in the green area Cr(n)≥Br(n)C_r(n) \ge B_r(n), meaning ⌈nr⌉\left\lceil{\sqrt{\frac{n}{r}}}\right\rceil is a valid fit‑height point for nn.

Since this criterion doesn’t cover all possibilities, the ratio between the number of valid points in the green area and the total number of points provides a lower bound for the probability that bb is a valid point:

Pr≥lim⁡n→∞∣Sn∣nSn={ k∈[n]:Cr(k)≥Br(k) }\begin{align*} P_r \brk{&}\ge \lim_{n \to \infin} \frac{\left|S_n\right|}{n} \brk[0]{\qquad} \brk S_n \brk{&}= \Set{k \in [n] : C_r(k) \ge B_r(k)} \end{align*}

We can approximate by counting points up to a certain nn. For example P1,n=10≥410P_{1,n=10} \ge \frac{4}{10} and P3,n=26≥2126P_{3,n=26} \ge \frac{21}{26}.

But we can’t count to infinity. Enter asymptotic density: a measure of how big a subset of N\N is relative to N\N! For our solution set SS its density is:

d(S)=lim⁡n→∞∣Sn∣n≤Prd(S) = \lim_{n \to \infin}\frac{|S_n|}{n} \le P_r

Exactly what we need. To compute d(S)d(S) we use that Cr(n)C_r(n) is equidistributed modulo 1. Equidistribution modulo 1 implies that, for constant t∈[0,1)t \in [0, 1):

lim⁡n→∞∣{ Cr(k):k∈[n] }∩[t,1]∣n=1−t\begin{align*} \lim_{n \to \infin}\frac{\left|\Set{ C_r(k) : k \in [n] } \cap [t, 1]\right|}{n} \brk{\\[0.5em]} = 1 - t \end{align*}

This tells us that a percentage of 1−t1 - t points out of nn are in [t,1][t, 1]. One can roughly notice this on the graph: the points (n,Cr(n))(n, C_r(n)) are distributed uniformly between the green and blue areas, proportionally with their sizes.

The limit’s numerator is equivalent to ∣{ k∈[n]:Cr(k)≥t }∣\left|\Set{k \in [n] : C_r(k) \ge t}\right|. For t=Br(k)t = B_r(k) this would’ve been precisely SnS_n, with the limit then giving us d(S)d(S) directly, but tt must be constant. To find an appropriate value, let’s bound Br(n)B_r(n):

12r≤Br(n)=12r+14r2+nr−nr=12r+nr(1+14rn−1)≤12r+nr⋅18rn=12r+18rrn\begin{align*} \frac{1}{2r} \brk{&}\le B_r(n) \brk &= \frac{1}{2r} + \sqrt{\frac{1}{4r^2}+\frac{n}{r}} - \sqrt{\frac{n}{r}} \\ &= \frac{1}{2r} + \sqrt{\frac{n}{r}}\left(\sqrt{1 + \frac{1}{4rn}} - 1\right) \\ &\le \frac{1}{2r} + \sqrt{\frac{n}{r}}\cdot\frac{1}{8rn} \\ &= \frac{1}{2r}+\frac{1}{8r\sqrt{rn}} \end{align*}

The approximation 1+x≤1+x2\sqrt{1 + x} \le 1 + \frac{x}{2} was used. Observe that the second term vanishes as n→∞n \to \infin. There may be an initial finite interval on which it excludes numbers, but for the remaining infinite tail it changes nothing. Since the density of a finite subset of integers is 00, we can ignore that segment when computing d(S)d(S). The effect is also visible on the graph early on.

This means we can simply take t=lim⁡n→∞Br(n)=12rt = \lim_{n \to \infin} B_r(n) = \frac{1}{2r}. Our final result is:

Pr≥d(S)=lim⁡n→∞∣{ Cr(k):k∈[n] }∩[12r,1]∣n=1−12r\begin{align*} P_r \brk[2,]{&}\ge d(S) \brk[2,] \brk[2,]{&}= \lim_{n \to \infin}\frac{\left|\Set{C_r(k) : k \in [n]} \cap [\frac{1}{2r}, 1]\right|}{n} \brk \brk[2,]{&}= 1 - \frac{1}{2r} \end{align*}

As a final note, attempting to exclude points where Cr(n)=0C_r(n) = 0, i.e. nr∈N\sqrt{\frac{n}{r}} \in \N, would’ve not influenced the result. nr∈A\frac{n}{r} \in A, where A={ p2  |  p∈N }A = \Set{ p^2 | p \in \N } the set of all squares, and since ∣A∩[n]∣≤O(n)|A \cap [n]| \le \mathcal{O}(\sqrt{n}), d(A)=0d(A) = 0. Our set of points is a subset of that, so it must also be density‑zero.

Thus, for the examples above P1≥0.5P_1 \ge 0.5 and P3≥0.833P_3 \ge 0.833. Desmos for the graph here.

The first conclusion is that fit‑height solutions will for the most part have bh=⌈nr⌉b_h = \left\lceil{\sqrt{\frac{n}{r}}}\right\rceil. We can derive even more interesting information by looking at the graph for r<1r < 1:

Note that r<1r < 1 means we’ve essentially flipped dimensions: the fit‑height points correspond to the fit‑width points of ratio 1r\frac{1}{r}. For r=12r = \frac{1}{2} as depicted above, P12≥0P_{\frac{1}{2}} \ge 0. How do we interpret this?

For r≥2r \ge 2, no a = ⌈rn⌉\left\lceil{\sqrt{rn}}\right\rceil satisfies the sufficient condition above to fulfill the fit‑width solution requirements.

Any valid awa_w will be greater than ⌈x0⌉\left\lceil{x_0}\right\rceil with very high certainty, especially when considering the growth rate of 12r\frac{1}{2r} as r→0r \to 0. This also provides an intuitive explanation for the second algorithm’s runtime: as rr grows the fit‑width solutions are farther and farther away from (x0,y0)(x_0, y_0), so the first loop will have to iterate more; at the same time, the probability that the initial fit‑height solution candidate is valid rapidly increases, which prevents the second loop from iterating.

The final conclusion is: for r≥1r \ge 1 it is very likely that bh=⌈nr⌉b_h = \left\lceil{\sqrt{\frac{n}{r}}}\right\rceil is a valid fit‑height point and almost never likely that aw=⌈rn⌉a_w = \left\lceil{\sqrt{rn}}\right\rceil is a valid fit‑width point. Then mostly bw<bhb_w < b_h, since with more columns the grid requires less rows to fit all squares. Therefore by (17)\text{(17)} for r≥1r \ge 1 the fit‑width solution is in the majority of cases better than any fit‑height solution. Likewise for r<1r < 1 but with fit‑width and fit‑height swapped.

Using binary search in the second algorithm

According to (18)\text{(18)} the algorithm always finds a solution after ⌊r⌋+1\left\lfloor{r}\right\rfloor+ 1 iterations, thus a0≤aw<a0+r+1a_0 \le a_w < a_0 + r + 1, where a0=⌈rn⌉a_0 = \left\lceil \sqrt{rn} \right\rceil is the starting value for awa_w.

We can binary search over that interval using the same loop condition from (17)\text{(17)}. If the midpoint is not a valid awa_w, we search in the upper half, since we’re not yet in the solution space, otherwise we search in the lower half, since we want the minimal solution. Here is the algorithm for awa_w:

const r = w / h;

let left = Math.ceil(Math.sqrt(r * n));
let right = Math.ceil(left + r + 1);

while (left < right) {
  const mid = Math.floor(left + (right - left) / 2);
  if (mid < r * Math.ceil(n / mid)) {
    left = mid + 1;
  } else {
    right = mid;
  }
}

return w / left;

Upper bound ceiled so interval is open. left stores awa_w. This reduces the asymptotic runtime to O(log⁡r)\mathcal{O}(\log r). Useful for very large ratios but very large ratios seem utterly useless.

⌊⋅⌋\left\lfloor \cdot \right\rfloor and ⌈⋅⌉\left\lceil \cdot \right\rceil are residuated mappings

This means that, for ∀x∈R,n∈N\forall x \in \R, n \in \N:

  1. n≤x  ⟺  n≤⌊x⌋n \le x \iff n \le \left\lfloor x \right\rfloor
  2. x≤n  ⟺  ⌈x⌉≤nx \le n \iff \left\lceil x \right\rceil \le n
  3. n<x  ⟺  n<⌈x⌉n < x \iff n < \left\lceil x \right\rceil
  4. x<n  ⟺  ⌊x⌋<nx < n \iff \left\lfloor x \right\rfloor < n

To prove the first, if x∈Nx \in \N then clearly n≤⌊x⌋=xn \le \left\lfloor x \right\rfloor = x, else if x∈R∖Nx \in \R \setminus \N:

n≤x  ⟺  n<x  ⟺  n<⌊x⌋+{x}  ⟺  n≤⌊x⌋∨(⌊x⌋<n<⌊x⌋+{x})  ⟺  {x}<1n≤⌊x⌋∨(⌊x⌋<n<⌊x⌋+1)  ⟺  n∈Nn≤⌊x⌋\begin{align*} \brk{&}n \le x \iff n < x \brk \iff &n < \left\lfloor x \right\rfloor + \{x\} \\ \iff &n \le \left\lfloor x \right\rfloor \lor (\left\lfloor x \right\rfloor < n < \left\lfloor x \right\rfloor + \{x\}) \\ \overset{\{x\} < 1}{\iff} &n \le \left\lfloor x \right\rfloor \lor (\left\lfloor x \right\rfloor < n < \left\lfloor x \right\rfloor + 1) \\ \overset{n \in \N}\iff &n \le \left\lfloor x \right\rfloor \end{align*}

The others are proven in a similar fashion. Read more about this on Wikipedia’s “Equivalences” for floor and ceiling. These are standard properties but I insisted on writing them here as a “note to self” since I’ve confused myself and applied them wrong way too many times. I probably know that Wikipedia page now by heart.

>