2
$\begingroup$

Suppose we have a rectangle with sides $a$ and $b$, $a, $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?

  • 0
    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.2012-08-11
  • 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.2012-08-12
  • 0
    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 problem2012-08-12
  • 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.2013-05-01
  • 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?2013-05-01
  • 1
    @Alex Ravsky I think the bound is $n(a,b) \le ⌈a/2⌉+⌈b/2⌉+⌈\sqrt{(a^2+b^2)}/4⌉$. However, it can be improved a little bit. Let $A,B,C,D$ be the vertices. You take [the Steiner tree](http://en.wikipedia.org/wiki/Steiner_tree_problem) on $A,B,C$ and the perpendicular segment from $D$ to the diagonal $AC$. You can also take the Steiner tree of $A,B,C,D$. I have no idea which of these two constructions is better.2013-09-11
  • 1
    See https://en.wikipedia.org/wiki/Opaque_forest_problem, which is a simpler version of the problem yet is still open even for a square.2015-08-01
  • 0
    @pepan You are right. I'm sorry for the error. Thanks for the correction.2018-02-01

0 Answers 0