Bound on the sum of squared distances between points inside a semi-circle

There are $n$ points $(a_0, ..., a_{n-1})$ inside a half-disk of diameter $D$. I would like to prove that there exists a permutation of the $n$ points $(b_0, b_1, .., b_{n-1})=(a_{j_0},a_{j_1} \cdots a_{j_{n-1}})$ such that

$$\sum_{i=1}^{n-1} \operatorname {d}(b_{i-1},b_i)^2 \leq D ^2.$$

Here, $\operatorname {d}(\cdot,\cdot)$ denotes the euclidean distance between two points.

I tried to use analytic geometry, yet it doesn't help. And I think there is a nice combinatoric way to solve this...


This is a neat question and I do not know how to solve it. But I have some comments on it.

$\text{}$1. Normally it is better to assume that your $n$ points $(x_1, \ldots, x_n)$ are in the unit disk or unit square and ask for the minimum length of a Hamiltonian path, that is, the permutation $\pi$ that gives the maximum of$$\sum_{i = 1}^{n - 1} \text{dist}(x_{\pi(i + 1)}, x_{\pi(i)}).$$The maximum of these minima (taken over all $n$ point configurations on the unit square, say) is to be denoted by $\text{MIN}(n, \text{dist})$. In such cases you do not expect an exact answer, but an order of magnitude one.

$\text{}$2. In your case $\text{dist}$ is the square of the Euclidean distance. The case of the square grid shows that $\text{MIN}(n, \text{dist}^2)$ is at least $1$ (more precisely $1 - 1/n$). A the minimal Euclidean distance between $n$ points in the unit square (unit disc) is at most $1/\sqrt{n}$, one would expect $\text{MIN}(n, \text{dist}^2)$ to be at most a constant.

$\text{}$3. It is perhaps more natural to consider the usual Euclidean distance. Then one can prove (by induction on $n$, for instance) that$$\text{MIN}(n, \text{dist}) \le \text{const} \cdot \sqrt{n}$$which is the best possible (as the square grid shows).

$\text{}$4. One can ask for the minimum length Steiner tree on these $n$ points, let $\text{STEIN}(n, \text{dist})$ denote this. This is easier to handle (as you will have no problem convincing yourself). For instance $\text{STEIN}(n, \text{dist})$ is about $\sqrt{n}$ and $\text{STEIN}(n, \text{dist}^2)$ is a constant and$$\text{MIN}(n, \text{dist}) < \text{STEIN}(n, \text{dist}) < 2\text{MIN}(n, \text{dist}).$$This latter inequality does not seem to extend to the $\text{dist}^2$ case. If it does, it would imply that $\text{STEIN}(n, \text{dist}^2)$ is a constant.

$\text{}$5. There are some related results, for instance a paper by Erdős and Fejes Tóth (1956?), a paper by Ajtai, Komlós, Tusnády (1984?), and many others in the area of the travelling salesman problem (more algorithmic aspects though).