A square of side 1 is given, and 10 points are inside the square.

If we divide the square into 9 smaller squares, and apply Dirichlet principle, we can prove that there are 2 of these 10 points whose distance is at most $\sqrt2/3$.

Can this statement be improved, in the sense that $\sqrt2/3$ can be replaced with lower value?

(This question came to my mind while reading some other similar questions here. I have no idea what would be a good approach.)

  • $\begingroup$ How about using a square of side 3. Then, the answer will look/be simpler but the logic remains the same. $\endgroup$ – Mick May 11 '14 at 11:14
  • $\begingroup$ www.packomania.com has lots of information about this problem. $\endgroup$ – gnasher729 May 11 '14 at 16:20

Putting $10$ points in a square of size $1$ such that the minimal distance $d_{\text{min}}$ between two points is maximized, is exactly the same as finding an arrangement of $10$ non-overlapping disks of radius $r=d_{\text{min}}/2$ with center in the unit square with the maximum radius possible (look at the second picture below). Note that these disks are getting out of the unit square but form the most dense packing of $10$ spheres of the square of size $1+2r$. So the problem is equivalent to the disk packing in a square. According to wikipedia (or directly the exhaustive main reference of the wikipedia article), the best known packing of $10$ spheres in a square gives us a minimal distance $$d_{\text{min}}= 0,421...$$ This is significantly better then the original bound $\sqrt{2}/3=0.47...$ found by the grid and pigeon hole principle.

enter image description here

Before finding the Wikipedia article I played with geogebra and the best packing I found is the one below, one can compute the radius and find $d_{\text{min}}=(\sqrt{2 \left(1+2 \sqrt{2}\right)}-2)/(2 \left(2 \sqrt{2}-1\right))=0.419...$ which is not as good as the one mentioned aboved (you want to maximize $d_{\text{min}}$).



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.