Find the maximum number of points inside a 3 by 4 rectangle (the points CAN also lie on the perimeter) with the constraint that no two points have a distance less than one.
someone suggested the following solution:
we consider the side of length 3 and we pick 4 points evenly distributed (including the endpoints) and we can do the same for the other side but with 5 points , and partition the rectangle into 12 unit squares to finally get that the maximum number of points is 20
- How can we prove that this arrangement guarantees the maximum number of points?
- Is there a way to generalize and solve this problem for any m by n rectangle, or to use other shapes (like rectangles , trapazoids etc..)?
please put more Tags for this problem as you see fits.
If we place a disk with radius $\frac 12$ on each point, the constraint is now that that no two disks can intersect (and their centers must lie inside the rectangle). This is now a circle packing problem. It's well-known that the optimal circle packing is hexagonal, so I would suppose that the answer to the question is along those lines.
I think that in the particular case of the 3 by 4 rectangle, there is no better packing. However, for larger shapes, the optimal packing will approximate a hexagonal one.