Minimizing the sum of the six distances determined by four points in the plane, if each distance is at least $d$
I give an alternative solution without numerical solvers.
The four points form a quadrangle. Let me first show that the optimal configuration forms a convex quadrangle. A configuration of four points in which no order of the vertices forms a convex quadrangle is a triangle with a point on the inside, see picture below:
Suppose first that one of the three diagonals has a length larger than $d$. Without loss generality, assume that $CD$ has a length larger than $d$. At least one of the sides $AC$ and $BC$ has a length larger than $d$. If not, the four points form a convex quadrangle. Without loss of generality, assume that $AC$ has length larger than $d$. By rotating $C$ around $B$ towards $A$ we reduce $AC$ and $CD$; hence the configuration is not minimal.
So we can assume that all three diagonals have length $d$, so we are in a configuration of three isosceles triangles with equal sides $d$.
At least one of the sides of the triangle has a length larger than $d$, otherwise one of the diagonals has length smaller than $d$. So assume without loss of generality that $AC$ is the largest of the three outside edges. This means that the angle $ADC$ is at least $\frac{2\pi}{3}$; hence $AC$ is at least $\sqrt{3}d$. If $AC > \sqrt{3}d$, then $P > 5d + \sqrt{3}d$; which is not minimal because you have found a better configuration. If $AC=\sqrt{3}d$, then at least one of the angles $CDB$ and $ADB$ is $\geq \frac{2\pi}{3}$. So at least one side of $BC$ and $AB$ has length $\geq \sqrt{3}d$. This means that $P \geq 4d + 2\sqrt{3}d > d(5 + \sqrt{3})$. This proves that this configuration is not minimal. This shows that in the minimal configuration the four points form a convex quadrangle.
Now I prove that in the minimal configuration, the four points form a rhombus. If three sides are of length $d$ and one side has length larger than $d$, then we can shorten this side by one of the following actions:
- By only moving $A$, rotating $A$ around $B$.
- By only moving $D$, rotating $D$ around $C$.
The first action is possible if $AC$ is larger than $d$ and the second action is possible if $BD$ is larger than $d$. If both $AC$ and $BD$ are equal to $d$, then $AD$ has length $d$ as well; therefore at least one of these actions is possible. The result of the actions is:
- Moving $A$: everything stays the same, except $AC$ and $AD$ reduce.
- Moving $D$: everything stays the same, except $BD$ and $AD$ reduce.
This means that this configuration cannot be optimal.
Suppose now we have two adjacent sides of length $d$ and the other sides have length larger than $d$ (see picture below)
If we move $A$ on $AC$, while fixing the other points, then $AC$, $AB$, and $AD$ reduce in length, while the others stay the same. This action is only possible if $AC$ has length larger than $d$. If $AC$ has length $d$, then we can rotate $B$ around $C$ towards the diagonal $AC$ reducing the length of $AB$ and $BC$. Therefore, in all situations, this configuration cannot be optimal.
Suppose now we have two opposite sides of length $d$ and the other two sides have a length larger than $d$, see picture below.
By simultaneously moving $A$ and $B$ (by the same speed) in a direction perpendicular to $CD$, we decrease both diagonals and the sides $BC$ and $AD$. This action is only possible if both diagonals $AC$ and $BD$ have length larger than $d$. If one of the diagonals has length $d$ (without loss of generality assume that $AC$ has length $d$), then we can rotate $B$ around $A$ towards $AC$ to reduce the length of $BC$. This shows that in all cases that this configuration is not optimal.
Assume one side has length $d$ and all other sides have a length greater than $d$, see picture below.
If one of the diagonals has a length larger than $d$ (assume without loss of generality that $AC$ has length larger than $d$), then we can move $A$ on $AC$ towards $C$ to reduce the lengths of $AC$, $AB$, and $AD$. If both diagonals have a length $d$, then $AB$ has a length $\leq d$, which is a contradiction. Therefore this situation cannot be minimal.
If all sides are larger than $d$, then at least on diagonal is larger than $d$. By moving the outer points of this diagonal inwards we get a better configuration; hence it is not minimal.
Therefore you can assume that the points form a rhombus with side length $d$. Take one angle $\alpha$ of this quadrangle (the other are $\pi-\alpha$, $\alpha$, and $\pi-\alpha$).
The length of the diagonals are $d\sqrt{2-2*\cos(\alpha)}$ and $d\sqrt{2+2*\cos(\alpha)}$ (see for example wikipedia)
The diagonals are at least $d$ when $-\frac{1}{2} \leq \cos(\alpha) \leq \frac{1}{2}$; which is when $\frac{\pi}{3} \leq \alpha \leq \frac{2\pi}{3}$.
This means that to minimize $P$, we have to minimize $\sqrt{2-2*\cos(\alpha)} + \sqrt{2+2*\cos(\alpha)}$ on the interval $\left[\frac{\pi}{3}, \frac{2\pi}{3}\right]$.
The second derivative (w.r.t. the variable $\alpha$) of this function is
$$\frac{\cos(\alpha)}{\sqrt{2-2\cos(\alpha)}} - \frac{\cos(\alpha)}{\sqrt{2+2\cos(\alpha)}} - \frac{\sin^2(\alpha)}{(2-2\cos(\alpha))^{\frac{3}{2}}} - \frac{\sin^2(\alpha)}{(2+2\cos(\alpha))^{\frac{3}{2}}},$$
which is negative on the interval $\left[\frac{\pi}{3}, \frac{2\pi}{3}\right]$.
Therefore the function to minimize is concave; hence the minimum is obtained at the border of the interval, i.e., $\alpha=\frac{\pi}{3}$ or $\alpha=\frac{2\pi}{3}$.
Filling in one of those values for $\alpha$ we get that the minimum of $P$ is equal to
$$4d + d\sqrt{2-2\cos(\alpha_\min)} + d\sqrt{2+2\cos(\alpha_\min)} = d(5 + \sqrt{3}).$$
Let me phrase this as an optimization problem. There are at least two points that are distance $d$ apart, as otherwise you can contract the points and get a better solution. Let's assume point $A$ is at coordinate $(0,0)$ and $B$ is at $(0,d)$. So the challenge is to find points $C$ at $(v,w)$ and $D$ at $(x,y)$. I have phrased this as an optimization problem in AMPL format for $d=1$:
var v;
var w;
var x;
var y;
minimize total_distance: sqrt(v^2 + w^2) + sqrt(x^2+y^2) + sqrt(v^2+(w-1)^2) + sqrt(x^2+(y-1)^2) + sqrt((v-x)^2+(w-y)^2);
subject to min_dist_AC: sqrt(v^2 + w^2) >= 1;
subject to min_dist_AD: sqrt(x^2+y^2) >= 1;
subject to min_dist_BC: sqrt(v^2+(w-1)^2) >= 1;
subject to min_dist_BD: sqrt(x^2+(y-1)^2) >= 1;
subject to min_dist_CD: sqrt((v-x)^2+(w-y)^2) >= 1;
Then I let the global optimization solver Baron solve it:
*************************************************************
NEOS Server Version 5.0
Disclaimer:
This information is provided without any express or
implied warranty. In particular, there is no warranty
of any kind concerning the fitness of this
information for any particular purpose.
*************************************************************
Job 8432228 has finished.
You are using the solver baron.
Checking ampl.mod for baron_options...
Checking ampl.com for baron_options...
Executing AMPL.
processing data.
processing commands.
Executing on prod-exec-6.neos-server.org
4 variables, all nonlinear
5 constraints, all nonlinear; 12 nonzeros
5 inequality constraints
1 nonlinear objective; 4 nonzeros.
BARON 19.12.7 (2019.12.07): threads=4
BARON 19.12.7 (2019.12.07): 107 iterations, optimal within tolerances.
Objective 5.732032769
v = 0.866025
w = 0.5
x = 0.866026
y = -0.499992
This is exactly the solution you obtained. Since Baron found the globally optimal solution, this is proof that you cannot do better.