A few days ago, a certain government announced, as part of an incipient Covid-19 lockdown de-escalation plan, that they would allow citizens to gather in groups of up to 10 people at their homes, as long as the security distance of 2 metres was respected. In my effort to figure out just how disconnected the members of this government are from the reality of said citizens, I wondered how big a room I would need to hold a gathering of 10 people, all separated 2 metres apart from each other.
More generally, I would like to know how much space I would need to have $N$ points separated by a minimum distance $D$. By space, initially I was thinking of the area of for example a rectangle, or a (convex?) polygon in general, but then I realised I could "cheat" and put every point in a line and have a $D(N-1)\times 0$ rectangle with null area. So I have two possible "valid" statements for the problem:
- What is the side of the smallest square containing $N$ points separated by a distance of at least $D$ from each other?
- What is the smallest perimeter of a polygon (or convex polygon if preferred) containing $N$ points separated by a distance of at least $D$ from each other?
I have been thinking about it for a while, mostly about the square version, and I feel the answer may not be trivial. I think if $N=M^2$ is a perfect square then a square with side $D(M-1)$ would contain all points optimally in a grid. For example, for $N=9$ you would have this $2D$ side square:
But I don't think that if I add a single more point, then I would need to increase the each side by $D$. In fact, I think for $N=13$ the optimal may be this $2\sqrt{2}D$ side square, still smaller than the next $D$ increment to the side that would be optimal for $N=16$ ($3D$):
Is there a solution to each of these problems, or some closely related one?
Best Answer
This is the problem of how big a square you need to fit $N$ $1$ meter disks. This is a hard problem. Many results are at http://www.packomania.com/ If you just look at the pictures you can see that the best known packing is often not symmetric. In particular, for $n=10$ the best known packing is into a square about $6.4764$ meters on a side. You can subtract $2$ in each direction as the edge people do not need to be $1$ meter from the wall, giving a $4.4764$ meter square.The specific packing is not easy to describe.
For large $N$ you can just assume hexagonal packing. Each person then occupies an area of $2 \sqrt 3$. There is some error along the edge, but that goes down as $N$ gets large.