# Find rectangle of minimum area where dimensions are larger than minimum

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?

• Do we have queries of the form $(a,b)$ ? – preetsaimutneja Jul 11 '14 at 7:21
• Are you allowing preprocessing? You obviously can't do this in better than linear time, otherwise, since you need to look at all the rectangles at least once. – David Richerby Jul 11 '14 at 11:04
• @DavidRicherby Right, this implies that the OP is allowing preprocessing, since otherwise the answer is NO. Also, the restriction on space complexity is needed to rule out the trivial $O(\log n)$ solution requiring quadratic memory. – Yuval Filmus Jul 11 '14 at 12:15
• Pre-processing is allowed, as long as it is bound by memory complexity of up to $O(n)$, and hopefully under $O(n log n)$ runtime complexity. – scooz Jul 11 '14 at 19:40

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})$.
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.