1
$\begingroup$

Given a circle of diameter D, how do you find the dimensions of a 2-dimensional grid that guarantees that at least one grid square is contained entirely within the circle, no matter where on the grid the circle is located?

Edits So far I've tried finding a square that fits within the circle by finding the radius and using the Pythagorean Theorem to find the largest square that fits entirely within the circle, but this only works when the circle and square are centered at the same point.

My latest attempt took the square above (a square inscribed into a circle), and dividing into 8ths. This puts the grid size at (D^2)/16. This feels like it works, but I don't know how to find a way to prove it.

$\endgroup$
5
  • 1
    $\begingroup$ Do you have any ideas? A lower and upper bound, perhaps? $\endgroup$ – Arthur Mar 8 '18 at 18:32
  • $\begingroup$ Worst case scenario the diagonal of the square is $D/2$, so the side is $D/(2\sqrt2)$ $\endgroup$ – Arnaud Mortier Mar 8 '18 at 18:32
  • 1
    $\begingroup$ Give us more details about what you have tried and more details about the problem itself. $\endgroup$ – Mehrdad Zandigohar Mar 8 '18 at 18:36
  • $\begingroup$ @ArnaudMortier The problem with that is it only works if the square and the circle are centered at the same point. $\endgroup$ – MailOrderBobcat Mar 8 '18 at 18:39
  • $\begingroup$ And I claim that this is the worst that can happen. Edit: I think that you misinterpreted my post. $\endgroup$ – Arnaud Mortier Mar 8 '18 at 18:49
0
$\begingroup$

Let $\ell=2a$ be the grid size and $r={d\over2}$ be the radius of the disc $D$. We may assume $D$ centered at $O=(0,0)$. The grid squares $Q_i$ have centers $(u_i,v_i)$. The square $Q_i$ is contained in $D$ iff $$\bigl(|u_i|+a\bigr)^2+\bigl(|v_i|+a\bigr)^2\leq r^2\ .\tag{1}$$ Now we can always find a center $(u_i,v_i)$ with $|u_i|\leq a$, $\>|v_i|\leq a$, but cannot rely on having $<$ in one of these inequalities. It follows that we need $$(2a)^2+(2a)^2\leq r^2$$ in order to guarantee the existence of a center $(u_i,v_i)$ satisfying $(1)$. Therefore the grid size $\ell$ has to satisfy $$\ell\leq{d\over 2\sqrt{2}}$$ in order to make sure that we have a grid square $Q_i\subset D$.

$\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.