Find rectangle of minimum area where dimensions are larger than minimum

Question

Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = x_i * y_i$) where $(x_i \geq a)$ and $(y_i \geq b$) for any $(a,b) \in R^2$.

The naive solution $F(S,a,b)$ will solve this with $O(n)$ runtime complexity and $O(1)$ memory complexity: loop through all the rectangles that are larger than the minimum required values $(a,b)$ for $(x,y)$, remember the one with the smallest area $x*y$ and return that. This requires no preparation or indexing of any kind, just a simple loop (sorting according to area beforehand won't improve the $O(n)$ worst-case runtime complexity).

Can this problem be solved with an algorithm with faster than $O(n)$ runtime complexity and up to O(n) memory complexity?

Answer 1

One simple solution uses k-d trees. In preprocessing, prepare a sorted list $L$ of $x_i y_i$ as well as a three dimensional k-d tree $T$ storing the points $(x_i,y_i,x_iy_i)$; this can be done in time $O(n\log n)$ and takes up space $O(n)$. Given $a,b$, we do binary search on $L$ to find the least $c$ such that $T$ contains a point $(x_i,y_i,x_iy_i)$ with $x_i \geq a,y_i \geq b,x_iy_i \leq c$; each such query takes time $O(n^{2/3})$, for a total query time of $O(n^{2/3}\log n)$.

It's not clear whether we actually need a three dimensional k-d tree; if a two dimensional one suffices, then the running time could get down to $\tilde{O}(n^{1/2})$.

Answer 2

Similar to another answer, but with range trees (see wikipedia) if you are willing to accept $O(n (\log n)^2)$ space instead of $O(n)$ space. In that case, you perform the same range queries $x \geq a$, $y \geq b$, $xy \leq c$ to perform binary search on $c$ to find the minimal $c$ that produces a query result in your range tree. The advantage over kd-trees is that range queries take only $O((\log n)^2)$ time in a 3-d range tree, for a total complexity of $O((\log n)^3)$. If you are willing to increase storage by a poly-logarithmic factor above $O(n)$, this can be much faster in the worst case.