28
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ Sorry I'v edited $\endgroup$ – AEIOUY Jun 7 '17 at 9:34
  • $\begingroup$ What do you mean when you say "name" points? You mean there "exist" such points? Also, do you assume that $b_0 = M$ and $b_{n-1}=N$ for something like that? $\endgroup$ – Henry Jun 7 '17 at 9:41
  • 1
    $\begingroup$ The author means it is possible for you to draw a path between the $n$ points such that the inequality holds. I don't think it matters if $M$ and $N$ are included. I've tried some examples and it seems true for any set of points, but I haven't proved it yet. $\endgroup$ – Lazy Lee Jun 7 '17 at 9:44
  • $\begingroup$ @LazyLee Oh, I got it. Thanks. I misunderstood the problem. $\endgroup$ – Henry Jun 7 '17 at 11:07
  • 2
    $\begingroup$ Partial solution, if the points are ON the semi-circle. Now for three points A,B,C on a semi-circle, let B be the central point of those three. Then we have that $\angle ABC \geq \pi/2$. By the law of cosines, we then have that $AC^2 = AB^2 + BC^2 - 2 AB \; BC \cos \angle ABC \geq AB^2 + BC^2$. Now arrange ("rename") the points such that they go from left to right. Repeated application of the above inequality gives that $\sum \operatorname {d}(b_i, b_{i+1})^2 \leq d(b_0, b_{n-1})^2$ and this is $\leq |MN| ^2$. $\quad \qquad \Box$ $\endgroup$ – Andreas Jun 7 '17 at 12:39
2
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ $d^2$ is not a distance, you have not the triangle inequality, on the contrary, if one angle is obtuse, then you have the opposite inequality, so in general, if you add more points, the sum of $d(P_i,P_{i+1})^2$ diminishes. So the maximum is attained for relatively small $n$, therefore it gives some round numbers. For the unit circle it seems to be $6$ and for the unit square it should be 3, but it is very difficult to prove. One first step could be to prove that it suffices to consider points on the boundary (the proof given by Jack is far from conclusive). $\endgroup$ – san Jul 6 '17 at 19:00

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.