2
$\begingroup$

Given a positive real number $R$ and $n$ fixed points in a plane, find the largest possible value $M$ such that if the pairwise distance between the $n$ points is less or equal to $M$, there exists a circle of radius $R$ that contains all $n$ points.

I realize this is related to the smallest enclosing circle problem, but it is not the same. Basically, I have a set of points, and I know all the pairwise distances between them, and I am given a fixed radius. I want to be able to say that if the maximum pairwise distance between these points is less than $M$, then there is definitely a circle of radius $R$ that encloses all of them, where this M is as large as possible.

Obviously, for two points, the answer is $2R$. For three points, it gets more complicated, but using some geometry, I believe the answer is $\sqrt{2}R$ (as in $\sqrt{R^2 + R^2}$), but I haven't been able to prove it. I would like to generalize this to $n$ points, where I am fine with the answer being dependent on $n$.

My hypothesis is that $\sqrt{2}R \leq M \leq 2R$ for all $n$, but I would be mainly interested in how large $M$ can be made as the number of points increases.

$\endgroup$
0
$\begingroup$

I don't have a complete solution but I can prove that your conclusion for $n=3$ points is wrong. Suppose that the maximum pairwise distance between 3 points is $M$. WLOG, suppose that the maximum distance $M$ is reached between points $A$ and $B$.

Where is the third point $C$? It has to be somewhere in the pink region. The borders of that region are segment $AB$ and two arcs, each encompassing $60^\circ$ with centers at points $A$ and $B$. Wherever you put the third point ($C',C''$), you can always cover the whole triangle with the blue circle. But the blue circle cannot be any smaller because in that case it could not cover the triangle $ABC$. And in that case:

$$M=R\sqrt{3}$$

enter image description here

$\endgroup$
  • $\begingroup$ Thanks! Just realized my flaw for the $n=3$ case. Theoretically, since points can be arbitrarily close together, I think $M$ cannot be any larger than $R\sqrt{3}$, and since adding more points only puts more restrictions on where the next one can go, I don't think $M$ gets any smaller, either. For my practical application, though, it would be interesting to see if $M$ could be made larger with a relatively high probability for points that are reasonably "spread out." $\endgroup$ – Dennis Mar 27 at 21:07
  • $\begingroup$ @Dennis If you find the answer useful, consider upvoting it, you don’t have to accept it. $\endgroup$ – Oldboy Mar 27 at 22:19
  • $\begingroup$ I did. Just didn't register because apparently I don't have enough "reputation points" or whatever. $\endgroup$ – Dennis Mar 27 at 22:31

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.