3
$\begingroup$

Consider $n$ points $\{p_i\}_{i=1}^n$ located inside or on a circle with radius $r$ in the plane. The question is: how to place the $n$ points so that the sum of inter-point distances, $$J=\sum_{i=1}^n\sum_{j=1}^n \|p_i-p_j\|^a,$$ is maximized? Here, $a$ could be 1 or 2.

The intuition is that the optimal solution is that all the points should distribute evenly on the circle. Any hints about it? Thanks.


Another relevant problem is: what if these points are located on the surface of a sphere instead of the plane? In particular, the points should be within a bounded area on a sphere and the distance is the length of the shortest arc connecting the two points instead of Euclidean distance.

$\endgroup$
4
  • 2
    $\begingroup$ For, $a=2$, $J=n\sum_{i}r_i^2 -[S_x^2+S_y^2+S_3^2]$ where, $r_i$ is the distance from the origin and $S_{x,y,z}=\sum_{i} \{x,y,z\}_i$. Hence, it will be maximum iff $(S_x,S_y,S_z)=\vec{0}$ and distances are maximum possible. This happens only when all the points are on the circle and forms a regular $n$-gon. $\endgroup$
    – Alapan Das
    May 9 at 15:45
  • $\begingroup$ @AlapanDas not only, it happens when they are on the circle and 0 is barycentre $\endgroup$ May 10 at 8:49
  • $\begingroup$ @Fedor Petrov, oh, I see. Thank you for correcting me. I had mistakenly assumed the barycentre at 0 as the points making regular $n$-gon on the sphere. $\endgroup$
    – Alapan Das
    May 10 at 9:09
  • $\begingroup$ I believe the new question (on a sphere) is sufficiently different that it would be better asked in a separate question. $\endgroup$ May 10 at 11:58
2
$\begingroup$

Let 0 be the centre of your circle of radius $r$.

If $a=2$, we expand the brackets and write $\sum_{i,j} (p_i-p_j)^2=2n\sum p_i^2-2(\sum p_i)^2\leqslant 2nr^2$, with equality if and only if all points lie on a circle and 0 is a barycentre.

If $a=1$, we again may suppose that they lie on circle (since the function $x\to\|p-x\|$ is convex, the sum of such functions is maximized when all points lie on the boundary of the disc they belong to.) So, they form a convex cyclic $n$-gon, without loss of generality their order is $p_1p_2\ldots p_n$. For each $j=1,2,\ldots,\lceil n/2\rceil$ the cyclic sum of $\|p_i-p_{i+j}\|$ is maximized for the regular polygon. Indeed, if you denote by $2\varphi_i$ the angle measure of the arc $p_ip_{i+1}$ (not containing $p_{i+2}$), so that $\sum \varphi_i=\pi$, you should maximize $\sum \sin (\varphi_{i}+\varphi_{i+1}+\ldots+\varphi_{j-1})$. All arguments of the sine function $\varphi_{i}+\varphi_{i+1}+\ldots+\varphi_{j-1}$ belong to $[0,\pi]$, and their sum is fixed and equals $j\pi$. Since sine is concave on $[0,\pi]$, the sum of sines is maximal when all sums are equal to $\pi j/n$. This is the case for a regular polygon, and already for $j=1$ this holds only for regular polygons.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.