Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this problem: given a set of rectangles $\{R_1, R_2...R_n\}$, and a new rectangle $R_q$, find where to put $R_q$ so it intersects (it does not matter how much area) the maximum number of the rectangles in the set. An answer will be very appreciated, thanks!

share|cite|improve this question
How an where rectangles $R_1,\, R_2,\,\ldots\,,R_n$ are situated? What restrictions are imposed for $R_q$? – M. Strochyk Sep 17 '12 at 20:03
I´m considering the problem in 2d. There are no restrictions on the set {R1,R2...Rn}, they can have any size, be anywhere, and intersect with each other. The only restriction about Rq is that it has a fixed size. – aleburzyn Sep 17 '12 at 20:15
A fixed size, independent of the other $n$ rectangles? Then at best I can guarantee $R_q$ will intersect one of the $R_n$, in the case that the first $n$ are all very far apart. – Kevin Carlson Sep 17 '12 at 21:08
That's correct, however I'm trying to solve the problem in an average case where the R1..Rn are near each other, and Rq does not have a very small size. I'm not worrying about the border cases. – aleburzyn Sep 18 '12 at 1:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.