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
6
+25
$\begingroup$

Instead of giving a proof, I will do two things:

  1. Generalize the question and give some conjectures on the generalization.

  2. Describe the strategy that I consider most promising at the moment, in order to prove the original statement. This strategy would also be useful to prove some of the generalizations.

Let $K\subset \Bbb{R}^2$ be a convex compact set. For any $n\in\Bbb{N}$, $X\in (X_1,\dots,X_n)\in K^n$ and $Q=(Q_0,Q_1)\in K^2$ with $d(Q_0,Q_1)=D(K)$, the diameter of $K$, we define $$ L_n(X)=\min_{\sigma\in S_n}\sum_{i=1}^{n-1}d(X_{\sigma(i)},X_{\sigma(i+1)})^2 $$ and $$ L_n^0(X,Q)=\min_{\sigma\in S_n}\left(d(Q_0,X_1)^2+d(X_n,Q_1)+\sum_{i=1}^{n-1}d(X_{\sigma(i)},X_{\sigma(i+1)})^2\right) $$ Note that $L_n$ is not a convex function on $K^n$.

We furthermore define $$ L(K)=\max_{n\in\Bbb{N}}\left\{ \max_{X\in K^n}\{L_n(X)\}\right\}\quad\text{and}\quad L_0(K)=\max_{n\in\Bbb{N}}\left\{ \max_{(X,Q)\in K^{n+2}}\{L_n^0(X,Q)\}\right\}. $$ Finally we define $$ q(K)=\frac{L(K)}{D(K)^2}\quad\text{and}\quad q_0(K)=\frac{L_0(K)}{D(K)^2}. $$

In this general framework, the original question reads: "Prove that $q(K)=1$ if $K$ is a half disk". From the definition it follows that $q(K)\le q_0(K)$, so it would suffice to prove that $q_0(K)=1$ in that case, since clearly $q(K)\ge 1$ for all $K$.

A set $X\in K^n$ is called optimal (for $q$) if $L_n(X)=L(K)$ and $(X,Q)$ is optimal (for $q_0$) if $L_n^0(X,Q)=L_0(K)$.

Now we will give conjectured values for some simple shapes of $K$.

  1. Equilateral triangle: $q(K)=q_0(K)=2$. Optimal set: vertices.

2.(**) Orthogonal triangle: $q(K)=q_0(K)=1$. Optimal set: $n=2$, the endpoints of the hypothenuse; $n=3$, vertices; there is also an optimal set for $n=4$.

  1. Rectangle with sidelengths $a<b$: $q(K)=1+\frac{a^2}{a^2+b^2}$, $q_0(K)=1+\frac{2a^2}{a^2+b^2}$. Optimal set: vertices.

  2. Square: $q(K)=\frac 32$, $q_0(K)=2$. Optimal set: vertices.

  3. Regular pentagon with radius $R$ and sidelength $S$: $q(K)=q_0(K)=\frac{2R^2+3S^2}{D^2}=\frac{55-17\sqrt{5}}{10}\approx 1.69868$. Optimal set: $n=6$, Vertices + center.

  4. Regular Hexagon: $q(K)=q_0(K)=\frac 32$. Optimal set: $n=3$, equilateral triangle; $n=7$, vertices + center.

7.a) Disk: $q(K)=\frac 12+\frac{3S^2}{4R^2}=\frac 12+\frac{3(5-\sqrt{5})}{8}=\approx 1.53647$, where $R$ and $S$ are the radius and the side length of an inscribed regular pentagon. Optimal set: 5 vertices and center of pentagon.

7.b) Disk: $q_0(K)=2$. Optimal set: $n=2$, square.

  1. Half disk: $q(K)=q_0(K)=1$. Optimal set: Vertices.

  2. Two equilateral triangles sharing one side: $q(K)=q_0(K)=1$. Optimal set: opposed far vertices.

The only proof I have is that of the orthogonal triangles. In that case the proof can be done by induction, cutting the triangle into two smaller orthogonal triangles.

The case of the hexagon shows that the optimal configuration can have at least one point in the interior, and in the case of the pentagon (and also in the case of the disk) there is no optimal set with all points on the boundary.

The case of the hexagon shows that a proof by induction has eventually to consider the step $n\mapsto n+4$, since for $n=4,5,6$ there is no optimal set $X\in K^n$ (except those sets with repeated entries).

${\bf STRATEGY:}$ In order to prove $q(K)=1$ for the half disk the present strategy relies on the truth of two conjectures: The first is that $$ q_0(K)=1. $$ Based on some numerical evidence we state the second conjecture:

There is no optimal set for $q_0$ in $K^{n+2}$ with $n$ different points if $n>3$.

The idea of the proof of the second conjecture is the following: Let $K=\{(x,y)\in \Bbb{R}^2,\ y\ge 0,\ x^2+y^2\le 1\}$. Then clearly $Q=((-1,0),(0,1)$ and assume that you have an optimal path $Q_0,X_1,X_2,X_3,X_4$. Then you will have restrictions on the angles and distances between the points that discard the existence of $X_5$, hence $X_4=Q_1$. However such a proof requires meticulous case-by-case analysis that I have been not able to perform (however I have already some restrictions for $X_1,X_2,X_3,X_4$).

The numerical evidence for the second conjecture is that when maximizing $L_4^0(X,Q)$ for $X\in K^4$ the solutions have always repeated points.

Once the second conjecture is proven, the cases $n\le 3$ are straightforward, although it requires some case-by-case study.

${\bf EDIT:}$

My assertion that the cases $n\le 3$ were straightforward was too bold (particularly the case $n=3$). The following analysis covers that cases. The last part has no formal proof, it was computed with the help of Mathematica.

We want to prove that $q_0=1$ for a half disk. So let $K=\{(x,y)\in \Bbb{R}^2,\ y\ge 0,\ x^2+y^2\le 1\}$ and $Q=((-1,0),(0,1))$. Note that for an optimal set $X$, the extremal points (vertices of the convex hull of $X\cup Q$) necessarily are on the perimeter, since otherwise we can change the set $X$ to $X'$ replacing $P_i$ by $P_i'=P_i/\|P_i\|$ for extremal points, and then the distance $d(P_i,P_j)^2$ increases strictly if $P_i$ or $P_j$ is an extremal point and remains the same for other pairs, so $L_n^0(X')>L_n^0(X)$, which is impossible, since $X$ is optimal.

From this we know that if an optimal set has only one point on the perimeter, all the points are inside an orthogonal triangle, and so by that known case we have $L_n^0(X)=4$.

We will prove that $\displaystyle\max_{X\in K^{n}}\{L_n^0(X,Q)\}=4$ for $n=1,2,3$.

For $n=1$ let $X=\{P_1\}=\{(x_1,y_1)\}$ be an optimal set. If $x_1\notin\{-1,1\}$, then by the above remark $x_1^2+y_1^2=1$ and the theorem of Thales gives us the desired length.

For $n=2$, if the two points are on the perimeter, then $L_2^0(X)<4$, since one angle is obtuse. So only one point $P_1$ is on the perimeter, and the other point has to be exactly below $P_1$, otherwise we would have a path with an obtuse angle and then $L_2^0(X)<4$. We could also refer to the case of an orthogonal triangle.

For the case $n=3$, if there are three points on the perimeter, then $L_3^0(X)<4$, since one angle is obtuse. If only one point is on the perimeter, then the case of an orthogonal triangle shows that $L_3^0(X)\le 4$.

So we have to analyze the case in which two points $P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$ are on the perimeter, i.e.,$x_1^2+y_1^2=1= x_2^2+y_2^2$. We can also assume $x_1<x_2$. For the third point $(x_3,y_3)$ necessarily $x_1<x_3<x_2$, else we would have a path with an obtuse angle (for example, if $x_3\le x_1$, the path $Q_0,P_3,P_1,P_2,Q_1$ would have $L^2<4$).

We claim that necessarily $y_3=0$. I don't have the complete proof of that claim. One should be able to close this gap by discarding different regions of the half disk for $P_3$. For example if $y_3<\min\{y_1/2,y_2/2\}$, one can show that $y_3$ must be zero.

Now there are three possible paths that may minimize $L^2$, so we have three different functions depending on $x_1,x_2,x_3$: $$ f_1(x_1,x_2,x_3)=d(Q_0,P_1)^2+d(P_1,P_3)^2+d(P_3,P_2)^2+d(P_2,Q_1)^2=2(x_3^2-(x_1+x_2)x_3+3+x_1-x_2), $$ $$ f_2(x_1,x_2,x_3)=d(Q_0,P_1)^2+d(P_1,P_2)^2+d(P_2,P_3)^2+d(P_3,Q_1)^2=2(x_3^2-(1+x_2)x_3+3+x_1-x_1x_2-y_1y_2), $$ $$ f_3(x_1,x_2,x_3)=d(Q_0,P_3)^2+d(P_3,P_1)^2+d(P_1,P_2)^2+d(P_2,Q_1)^2=2(x_3^2-(x_1-1)x_3+3-x_2-x_1x_2-y_1y_2), $$ and $L_3^0(X)=\min\{f_1(x_1,x_2,x_3),f_2(x_1,x_2,x_3),f_3(x_1,x_2,x_3)\}$. Using that the three functions are quadratic in $x_3$ and playing around with the intersection of the corresponding parabolas, one can see that for a given pair $x_1,x_2$ there is a unique $x_3$ which maximizes $L_3^0(X)$. So we have a function $L(x_1,x_2)$. The plot of this function shows that the maximum is 4 and is attained when $x_1=x_2$, when $x_1=-1$, when $x_2=1$, or finally when $x_1$ and $x_2$ satisfy the fourth order equation $$ (1)\qquad\qquad\qquad\qquad\qquad(x_1+1)(1-x_2)(x_1-x_2-2)^2=(x_1-x_2)^2(1-x_1)(1+x_2). $$ The plot of this last case is a curve that runs near $(x_1-1)^2+(x_2+1)^2=4$. This can be seen when one plots the function $L(x_1,x_2)$ for $(x_1,x_2)\in [-1,1]\times [-1,1]$.

This proves numerically that $\displaystyle\max_{X\in K^{3}}\{L_3^0(X,Q)\}=4$. A formal proof following these ideas would have to prove rigourously that the maximum is attained effectively at these points, and that its value is 4.

${\bf Methodology\ for\ finding}$ $L(x_1,x_2)$.

For fixed $x_1,x_2$ we call $a$ the value of $f_1(x_1,x_2,x_3)=f_3(x_1,x_2,x_3)$ at the intersection of these two parabolas, similarly $b$ is the value of $f_1(x_1,x_2,x_3)=f_2(x_1,x_2,x_3)$ at the corresponding intersection and $c$ is the value of $f_2(x_1,x_2,x_3)=f_3(x_1,x_2,x_3)$ at the corresponding intersection. Then $L(x_1,x_2)=\min\{c, \max\{a, b\}\}$. The values for $a$, $b$ and $c$ are given by $$ a\text{:=}\frac{2 \left(x_1 \left(\sqrt{1-x_1^2} \sqrt{1-x_2^2}-x_2^2+1\right)-\sqrt{1-x_1^2} x_2 \sqrt{1-x_2^2}+x_1^2 (x_2-1)-x_2^2+x_2+4\right)}{x_2+1} $$ $$ b\text{:=}\frac{2 \left(x_1 \left(x_2^2-\sqrt{1-x_1^2} \sqrt{1-x_2^2}+1\right)+\sqrt{1-x_1^2} x_2 \sqrt{1-x_2^2}+x_1^2 (1-x_2)+x_2^2+x_2-4\right)}{x_1-1} $$ and $$ c\text{:=}2 \left(-\sqrt{1-x_1^2} \sqrt{1-x_2^2}+\frac{(x_1+x_2)^2}{(-x_1+x_2+2)^2}+\frac{(x_1-1) (x_1+x_2)}{x_1-x_2-2}-x_1 x_2-x_2+3\right) $$ Surprisingly (at least I was surprised) the maximum is attained at the curve given by (1) exactly when the three values $a$, $b$ and $c$ coincide, this means, when the three functions $f_1,f_2,f_3$ coincide, which means that the length of the three possible paths is the same. Maybe one can exploit this fact for a formal proof.

$\endgroup$
  • $\begingroup$ I suppose $Q_0$ and $Q_1$ in the definition of $L_n^0$ are actually $Q_1$ and $Q_2$. Also, what are $P_1$ and $P_n$? $\endgroup$ – Fimpellizieri Jul 11 '17 at 0:01
  • $\begingroup$ Typos corrected. $\endgroup$ – san Jul 11 '17 at 0:11
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).

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