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.

Suppose we have a rectangle with sides $a$ and $b$, $a<b$, $a,b \in \mathbb R$. What is the minimum number of circles centered in the rectangle with radius $1$ such that each line passing through the rectangle intersects at least one circle in at least one point?

I posed this problem a week ago and tried to solve it, however, I couldn't get anywhere. One obvious thing is that if we restrict the lines to be parallel to the sides of the rectangle, the answer will be $\left \lceil \frac{\left \lceil b \right \rceil}{2} \right \rceil$. Any ideas for the original problem?

share|improve this question
    
The subject title uses "covering a rectangle", which seems to be misleading given the problem statement, that one only asks each line "passing through the rectangle" to intersect at least one circle. Clearly it suffices to cover the perimeter of the rectangle. –  hardmath Aug 11 '12 at 21:25
1  
Thanks, edited. Also it suffices to cover two diagonals to have each line intersecting at least one of them, but I'm intersected in the minimum number of such circles. –  Goodarz Mehr Aug 12 '12 at 2:14
    
I'm not sure the combinatorics-related tags are really appropriate here, unless you have a specific way in mind to make this into a combinatorial problem –  Marc van Leeuwen Aug 12 '12 at 6:22
1  
I denote the required minimal number of circles as $n(a,b)$. It seems that we have the following bounds. $n(a,b)\ge\sqrt{(a^2+b^2)}/2$. This bound follows from the fact: if we orthogonally project all the circles of a required arrangement on a diagonal, the projections should cover it. –  Alex Ravsky May 1 '13 at 7:50
1  
$n(a,b)\le \lceil a/2\rceil+\lceil b/2\rceil +\lceil \sqrt{(a^2+b^2)/8}\rceil $. This bound follows from the fact: each line intersecting the rectangle $[0;a]\times [0;b]$ should intersect also the set $A=[(0,0);(a,0)]\times \{0\}\cup \{0\}\times [(0,0);(0,b)]\cup [(a/2,b/2);(a,b)]$ consisting of three segments. And we cover the set $A$ by the diameters of the circles. Can anybody improve these bounds? –  Alex Ravsky May 1 '13 at 7:51
show 1 more comment

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.