# Minimum space for N points at distance D

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?

• Smart presentation... – Jean Marie May 4 '20 at 12:59
• 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. – Ross Millikan May 4 '20 at 15:06

## 1 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.