Find rectangle of minimum area where dimensions are larger than minimum
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})$.