Smallest enclosing circle of points with minimum distance 1

areageometrypacking-problempolygonsrecreational-mathematics

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.

Best Answer

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.

Related Question