2
$\begingroup$

We have $n$ points in the plane, where the distance between each point is at least 1. What is the minimal enclosing circle of these points?

For $n = 1$ there is no answer, because there is no area to speak, and for $n=2$ the smallest circle would have a diameter of 1. For the rest, I first thought of the $n$-polygons. I first thought this holds true for $n = 3, \dots, 6$, but for $n=7$ one can fit an extra point the middle of the hexagon without violating the distance criteria. Therefore $n=6$ and $n=7$ have the same answers. I imagine this gets more and more interesting as $n$ increases, because there is more and more room for points in the middle of the polygons, but also more complicated.

The following table contains the values I have calculated. I use the fact that for an $n$-polygon with sidelengths 1, the radius of the encompassing circle is $\frac{1}{2\sin(\frac{\pi}{n})}$. The formulas when $n$ gets bigger are a bit complicated, so I have approximated the area.

$$\begin{array}{c|c|c} n & \text{Area} & \text{Shape of points}\\ \hline 2 & \frac14 \pi & \text{Line of length 1}\\ \hline 3 & \frac13 \pi & \text{Triangle with sidelengths 1}\\ \hline 4 & \frac12 \pi & \text{Square with sidelengths 1}\\ \hline 5 & 0.72\pi & \text{Pentagon with sidelengths 1}\\ \hline 6 & \pi & \text{Hexagon/pentagon with one middle point}\\ \hline 7 & \pi & \text{Hexagon with one middle point}\\ \hline 8 & 1.33\pi & \text{Heptagon with one middle point}\\ \hline \end{array}$$

Since the problem involves points with a fixed distance, I thought of sphere packings in 2D first. This problem is different in several ways: we don't want to minimize the enclosing circle of circles, but only focus on the enclosing circle of the sphere centers.

I think maybe this can be solved with an algorithm based on what I have read about the more general problem of finding the smallest enclosing circle of any set of points, but then you would first have to find the optimal way to configure the points either way.

I thought about this because of social distancing, if every person keep 1 meter distance, what this the minimum space occupied by $n$ people?

Any input would be greatly appreciated.

$\endgroup$
1
$\begingroup$

This is equivalent to the problem of packing equal circles in a large circle. Suppose the smallest enclosing circle in your problem has radius $r$, then the smallest circle in which $n$ unit circles can be packed has radius $2r+1$.

Some solutions for the latter problem are given here and here.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have trouble seeing the equivalence between the two problems. I can see that it is correct for all my examples, but it doesn't feel intuitive why it is correct. Could you provide an explanation of why they are equivalent? $\endgroup$ – jaykopp Apr 7 at 17:34
  • $\begingroup$ @jaykopp Draw a circle of radius $\frac12$ around each point in your formulation. Then increase the smallest enclosing circle's radius by $\frac12$ too, and make it a container. The result is a circle packing (points on the boundary become circles tangent to the container). This can be reversed. $\endgroup$ – Parcly Taxel Apr 7 at 17:37
  • $\begingroup$ I get how you move between the two, but how can one know for sure that the smallest circle packings are equivalent with the smallest encompassing circle in my problem? $\endgroup$ – jaykopp Apr 7 at 17:43
  • $\begingroup$ @jaykopp I said that circle packings can be transformed (reversed) into solutions for your problem. The best circle packing = the best solution for your problem. $\endgroup$ – Parcly Taxel Apr 7 at 17:44
  • $\begingroup$ I got it now. The key take away is that points on the boundary correlate with spheres tangent to the circle in the packing problem $\endgroup$ – jaykopp Apr 7 at 17:47

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.