Packing Points into Region

Question

In a $64\times 200$ region, the distance between any two points must be at least $25$.

What is the maximum number of points that can be placed inside the region? The most I could fit was 30.

What if they were placed in the most space-inefficient way? (Least number of points present such that no more can be placed)

This has to do with random obstacle generation in a game I'm working on.

Answer 1

If the size of the rectangular region is $w = 64$ by $h = 200$, and $R = 25$ is the minimum distance between any pair of points, and points are allowed to reside on the perimeter of the region, then the number of points you can put within the rectangular region cannot exceed $N$, $$N \le \left \lfloor \frac{4 (w + R)(h + R)}{\pi R^2} \right \rfloor$$ because each point excludes a circular region whose area is $\pi\left(\frac{R}{2}\right)^2 = \frac{\pi R^2}{4}$.

In this case, $N \le \lfloor 40.794595 \rfloor$ i.e. $N \le 40$.

From circle packing, we know that not all "area" is used in this way; that you cannot cover all of a surface with non-overlapping circles. In practice, it means that the true, absolute number is somewhat less. (Even the shape, or aspect ratio of the rectangle, matters.)

I am not aware of any methods of finding the actual absolute number of circles/disks/points, because there is an infinite number of positions for each point within the area. Since this is for a game, I'd expect the above known absolute upper limit to suffice, and the actual number of obstacles to vary.

Answer 2

I can fit 26 of them if some of them are allowed to be on the edge, using hexagonal packing which is optimal for large regions (three columns lengthwise, two of 9 points each that touch the ends, interleaves with one columns of 8 points each). If you make this one unit wider, I could fit another column, and get 34. I suspect that if you take a 64x200 rectangle and slide it around a hexagonal pattern with the points 25 apart you will find an oblique angle where more than 26 dots are covered. But if you can change the region to 65x200, life will be much easier.

Answer 3

Since any two points cannot be closer than 25 units, picture each point as the center of a circle with a radius of 25 units, which is the same as a circle with a diameter of 50 units. 4 such circles could be placed one on top of each other in a 64-unit wide by 200-unit high area.

It might look something like this (You have to assume they're touching):

O
O
O
O

Along the top of the uppermost circle, you could have 3 points (upper left corner of the region, 25 units to the right of that point, and then another 25 units to the right).

Similarly, you could have another set of 3 points going through the center of the uppermost circle, and along the bottom of the uppermost circle. Each of these would be exactly 25 from its nearest neighbor. So, the first circle has given us 9 such points.

Each of the other circles is going to add another 6 such points (not 9, because the last set of 3 from the previous circle is the same as the first set of 3 from the new circle). So, that's 3 more circles with 6 points each, or 18 more points.

Adding this result to the previous 9, we get 27 points. I am unfortunately unable to prove this is a maximum, but it does seem like a good starting point.