Maximizing rectangle area without intersecting others I have a list $W$, of (non intersecting) rectangles where $W \ni w = (x, y, \text{width}, \text{height})$. The list is increasingly sorted by $y$-coordinates.
Given an input rectangle $R$, I would like to know how much $R$ can grow (maintaining aspect ratio) without intersecting with any of the other rectangles.
An example:

Here $W=\{D, B, C\}$ where $D=(10, 2, 2, 8)$, .. and $R=(1, 1, 1, 1)$, so its aspect ratio is $\frac{w}{h}=1$. R can grow its width to 8, because at 9 it intersects with D, but the height is maximized at 6. Therefore R can grow up to 6 times before it intersects with any of the other rectangles.
I'd like this function (or algorithm) to return 6 as the result.
Right now I'm doing the brute force approach, that is grow R once, check for each $w\in W$ if $w \cap R = \emptyset$ and repeat until the intersection is non-empty.
 A: Because $R$ maintains its aspect ratio, you know the line $L$ along which $R$'s upper-right corner tracks as it grows.  Identify all those rectangles that either lie above $L$, with some portion right of the leftmost coordinate of $R$,
or are intersected (from below) by $L$.  Sort their bottom edges vertically.  The lowest
bottom edge is the rectangle you'll hit above as $R$ grows.  
Repeat the same calculation for the rectangles right of $L$, sorting left edges to find the one first hit as $R$ grows.
Then take the smaller of the two growths.
In your example, $L$ has slope 1, $B$ is hit first above, $D$ is hit first to the right, but $B$ is hit before $D$.

As requested, here is an illustration, with the slope of $L$ $\frac{1}{2}$:


A: Your final sentence is basically knocking on the door...
You could write: Given n rectangles $A_1$ = $(a_{1},b_{1},c_{1},d_{1})$ , $A_2$ = $(a_{2},b_{2},c_{2},d_{2})$ , ... , $A_n$ = $(a_{n},b_{n},c_{n},d_{n})$ , then the largest possible square which doesn't intersect any of the squares $A_i$ ($1\leq$ i $\leq$ n) is $(1,1,M,M)$, where M = min{$a_{1}$, $a_{2}$, ..., $a_{n}$, $b_{1}$, $b_{2}$, ..., $b_{n}$} - 2.
This is the same thing as finding the minimum of the $a_{i}$, then finding the minimum of the $b_{i}$ and then you have M = (minimum of these two values) - 2
