3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do we have queries of the form $(a,b)$ ? $\endgroup$ – preetsaimutneja Jul 11 '14 at 7:21
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Jul 11 '14 at 11:04
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus Jul 11 '14 at 12:15
  • $\begingroup$ 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. $\endgroup$ – scooz Jul 11 '14 at 19:40
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.