Maximum Dispersion of a Connected Geometric Graph

Question

Let $\left\{\mathbf{p}_1,\dots, \mathbf{p}_k\right\}$ be a set of points in $n$-dimensional Euclidean space, and let the second moment of these points be defined as:

$ U=\sum \limits_{i=1}^{k} ||\mathbf{p}_i -\bar{\mathbf{p}}||^2, $

where $\bar{\mathbf{p}}$ is their centroid.

Let two points $i$ and $j$ be connected if $||\mathbf{p}_i - \mathbf{p}_j||\leq \lambda$.

Then, under the constraint that the points are to form a connected graph, what is the configuration that maximizes their second moment?

Answer 1

Notice that this is the same as maximizing $\sum_{i<j} |p_i-p_j|^2$. Also by rescaling assume that $\lambda =1$. Since your graph is connected there is a spanning tree whose vertices are the $p_i$'s. Let $\text{d}(i,j)$ denote the graph theoretic distance between $p_i$ and $p_j$ along this tree. From the triangle inequality $\sum_{i<j} |p_i-p_j|^2 \le \sum_{i<j} \text{d}(i,j)^2$. It is a nice combinatorial exercise to show that this last quantity is maximized when the tree is a path. Therefore your second moment is maximized when the points are all on a line so that $|p_1-p_2|=|p_2-p_3|=\cdots=|p_{k-1}-p_k|=1$.