2
$\begingroup$

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:

Example for nine points

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$):

Example for thirteen points

Is there a solution to each of these problems, or some closely related one?

$\endgroup$
2
  • $\begingroup$ Smart presentation... $\endgroup$ – Jean Marie May 4 '20 at 12:59
  • $\begingroup$ This is the problem of how big a square you need to fit $n$ unit disks. This is a hard problem. Many results are at packomania.com If you just look at the pictures you can see that the best known packing is often not symmetric. $\endgroup$ – Ross Millikan May 4 '20 at 15:06
2
$\begingroup$

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.

$\endgroup$

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.