Define an "almost square" as a rectangles with aspect ratio between $1/2$ and $2$. What is the minimal number of interior-disjoint almost-squares required to tile the following L-shape (where $n$ is an integer)?
Background: It is known (e.g. Richard Kenyon, 1996) that tiling an $n \times (n-1)$ rectangle with squares requires $O(\log n)$ squares. This number grows to infinity as $n$ grows. However, if we relax our requirements and agree to tile the rectangle with almost squares, then one almost-square is sufficient. In practical scenarios, almost-squares can be almost as good as squares, and their number (in this case) is significantly smaller.
My question is: Does this fact extend to more general polygons? Specifically, is it possible to tile the L-shape in the above diagram (which is an $n \times n$ square, missing a single $1 \times 1$ square at the corner) with axis-parallel almost-squares whose number is constant (independent of $n$)?
Note: This question is related: https://math.stackexchange.com/questions/873586/size-of-minimal-covering-overlapping-and-disjoint
Consider the problem as a tiling of an $n\times n$ square, where we have already fixed a $1\times 1$ in the corner. Given a partial placement of rectangles in the $L$-shape, let $a$ be the highest $x$-coordinate of any point on a rectangle and $b$ the highest $y$-coordinate of any point on a rectangle (where we parametrize the big square as $[0,n]\times [0,n]$).
Obviously, we start with $(a,b)=(1,1)$. Now, consider how $a$ and $b$ can change as we add rectangles. If we add the "wrong" rectangles, $a$ and $b$ will grow dramatically, but we can choose them in whatever order we like. Consider the rectangles occupying the points $(a+\epsilon,0)$ and $(0,b+\epsilon)$: the rectangles just on the "other side" of the current borders. They must be distinct from each other, and at most one of them can occupy the point $(a+\epsilon,b+\epsilon)$. Consider the other rectangle. If we add it, then one of $a$ and $b$ stays fixed, and the other increases by one of the dimensions of the rectangle, so we have either $(a,b)\mapsto (\le a+2b,b)$ or $(a,b) \mapsto (a,\le b+2a)$ (by the constraints on the ratio of our rectangles). Since we are trying to get $(a,b)$ as large as possible, we can forget about the $\le$ signs in these moves and just always pursue the maximum. Call these Move $1$ and Move $2$, respectively.
What is the fewest number of applications of Move $1$ and Move $2$ to get from $(1,1)$ to $(n,n)$? Note that if $a<b$, then the pair $(a+2b,b)$ is strictly larger than the pair $(a,b+2a)$ once we reverse the order of the latter (since our target is symmetric, we don't care about order). So the optimal strategy is to always alternate between Move 1 and Move 2, and our series of $(a,b)$ values goes $(1,1), (1,3), (7,3), (7,17), (41,17), \ldots$, with terms coming from $\text{A}001333$.
This puts a lower bound $k$ on the number of moves, which is asymptotically $\log_{1+\sqrt{2}}(n)$. But, conveniently, $k$ is also an upper bound!
To see this, note that we can easily add a rectangle at each step so that the rectangles placed so far completely tile the region $[0,a]\times[0,b]$, and then just clip off the final one or two rectangles when we exceed the bounds of our $n\times n$ square. So the only risk is that this clipping-off may bring the ratios outside of $[1/2,2]$.
Let $(a,b)$ be the furthest we get before either value exceeds $n$; WLOG, say $a<b$. With some thought, it is apparent that this only poses a problem for clipping if $b>n/2$; our solution is to shrink our $a\times b-2a$ rectangle so that its top border is at $y=n/2$, and proceed from there. Now our only concern is that this modification will have rendered the modified rectangle to have an unacceptable ratio, but with a bit of tedious algebra one can check that we're okay as long as $a\le 3b$, which is easily verified.
So the final answer is that the number of necessary rectangles is the smallest $k$ such that
$$\frac{(1-\sqrt{2})^k + (1+\sqrt2)^k}2\ge n$$