What arangement of $n$ points in the plane minimizes the dispersion of the distances between them?

Solution 1:

Not quite an answer (I'd be suprised if this problem can be solved analytically) but, I've playing a little:

This fiddle lets you play for different values of $n$. The minimization algorithm (not optimized!) has a "temperature" parameter (kind of a simulated annealing), higher values lets you escape from local minima.

Empirically, my findings agrees with yours: for $n = 4 \cdots 7$ the regular polygons win. For $n=8, 9, 10, 11$ it's the polygon with a central point - but for $n=11$ the configuration with two internal points is a quite deep (but still suboptimal) local minimum.

For $n=12$, the configuration $(10,2)$ (two internal points) is the optimal one, but $(11,1)$ and $(9,3)$ are relevant competitors.

For larger $n$ things get more complicated, with many similar local mimima.

For example, for $n=21$, the first configuration here $(15,5,1)$ is the main attractor, but there are other three importal local minima, and the last one $(16,5)$ seems to be the optimal.

For even larger values, the points tend to distribute all over the circle, as expected, but with higher concentration over the circumference. For $n=300$ I get $v=0.4604068$. Not too far from the upper bound limit $0.4834258476$ (where all the points lie on the circumference).

Visually, this appears to support Anders Kaseorg's answer, points seem to correspond to the projection of a uniform distribution over a sphere.

Solution 2:

If we assume that, in the limit as $n → ∞$, the optimal distribution of points converges to some rotationally symmetric distribution, and optimize a numerical approximation of this distribution, we find outrageously strong numerical evidence that the distribution appears to be the one you get by orthogonal projection onto a plane from the uniform distribution on the surface of a sphere.

(Plot of the predicted vs. optimized inverse CDF of the distance from the origin, normalized such that $\overline x = 1$.)

Consider the segment between two uniformly random points on the sphere of radius $r$ (before projection). Let $a$ be the cosine of the angle between the segment and the projection direction, and let $b$ be the cosine of the spherical angle between the points. Then $a$ and $b$ are independent uniformly random values between $-1$ and $1$. We can compute the planar distance between the projected points as $r\sqrt{1 - a^2}\sqrt{2 - 2b}$. So the mean planar distance is

$$\overline x = \frac14 \int_{-1}^1 \int_{-1}^1 r\sqrt{1 - a^2}\sqrt{2 - 2b}\,da\,db = \frac{πr}{3},$$

and the coefficient of variation is

\begin{multline*} v = \frac{3}{πr} \sqrt{\frac14 \int_{-1}^1 \int_{-1}^1 \left(r\sqrt{1 - a^2}\sqrt{2 - 2b} - \frac {πr}3\right)^2\,da\,db} \\ = \frac{\sqrt{12 - π^2}}{π} ≈ 0.464601123231588. \end{multline*}