Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have this problem: given a set of rectangles {R1,R2...Rn}, and a new rectangle Rq, find where to put Rq 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|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

 
discard

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

Browse other questions tagged or ask your own question.