Maximize smallest distance between any two of n points on a disk

112 Views Asked by At

How do you distribute n points in a disk such that the smallest distance between any two of the points is maximized?

Before 7, the solution is as simple as evenly distributing them along the perimeter of the disk, but at 7 the distance between two points distributed like that falls to 0.867, making it then more efficient to put one point in the center.

But what about 8? 9? Is there a general answer for arbitrary n? If not a general solution for the arrangement, what about for the maximum smallest distance?

1

There are 1 best solutions below

0
On BEST ANSWER

As explained in the comment by Jaap Scherphuis, no general solution is known. The specific cases for $n\le13$ have all been proved, and so is the solution for $n=19$. The last of these involves a highly symmetric "centered hexagonal" arrangement where one point is in the center, six additional points surround it forming a close-pack array, aad then twelve outer points surround those six. Analogous arrangements may be constructed for higher centered hexagonal numbers ($37,61,91,$ etc), but none beyond $19$ is a proved optimum.

Eight and nine versus ten

There is a neat way to prove that the optimal arrangement remains the one with a single interior point with eight or nine total points, but we begin to require more interior points when $n=10$. For the eight-point case, let $O$ be the central point and $A,B,C,...,G$ be the oiter points, initially arranged as a regular heptagon in rotational order. Now construct the circles through $A$ centered on $B$ and on $G$, which intersect at $A$ and at a second point $A'$ inside the disk. If we form $\triangle A'DE$, which has the largest circumradius among triangles with $A'$ as one vertex and remaining heptagonal points as the other two, we discover that this circumradius is less than the side of the original regular heptagon. This constrains us from moving $A',O$ in any way that would make them farther from the remaining heptagonal points and each other than the sides of the original heptagon. Spreading out the latter six points to fill the gap between $B$ and $G$ on the boundary only makes this circumradius problem worse. We ran a fool's errand distorting that heptagon. If we try the analogous operation with nine points, starting with a regular octagon $ABCDEFGH$ plus its center $O$, we find that $\triangle A'DE$ (or $\triangle A'EF$) still has too small a circumradius conpared with the sides of the octagon. Only with $n=10$ do we get a triangle with large enough circumradius to explore better solutions than the centered regular polygon.