Maximizing the Sum of the Distances between Four Points on the Unit Hemisphere^††thanks: Supported by NSFC under Grant Nos. 12071282, 61772203.

Assume that four points are placed on the hemisphere of the unit radius:

$$S^{2}_{\geq 0}:=\{(x,y,z)|x^{2}+y^{2}+z^{2}=1,z\geq 0\},$$

we want to find the largest value of the sum of distances between them. A similar problem for maximizing the sum of distances between $n$ points on the unit sphere has been studied by many people in past (see [1], [2], and [3] for example), where we can see that the problem for four points is very easy and for $n\geq 5$ it becomes very difficult. To our knowledge, the question for points on hemispheres seems not settled yet in the literature.

As we will prove in Lemma 1, if the sum of distances between four points is maximal, then the center of the sphere must lie in the interior or on one of the surfaces of the tetrahedron formed by the four points, which immediately implies that, as shown in Fig. 1, at least three of the four points must lie on the equator of the hemisphere:

$$S^{1}:=\{(x,y,0)|x^{2}+y^{2}=1\}.$$

Considering that the optimal configuration is invariant under the rotation around the $z$-axis, we can express the optimal problem to a non-linear programming as follows:

	$\displaystyle\max$		$\displaystyle f:=\sum_{0\leq i<j\leq 3}\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}+(z_{i}-z_{j})^{2}},$		(1)
	s.t.		$\displaystyle x_{i}^{2}+y_{i}^{2}+z_{i}^{2}=1,\;i=0,1,2,3,$
			$\displaystyle x_{0}=0,y_{0}=-1,z_{0}=z_{1}=z_{2}=0,\;z_{3}\geq 0.$

We may try to solve this problem by using the Lagrangian multiplier method and symbolic computer algebra. It is easy to prove that

$$A:=(0,-1,0),\;B:=(1,0,0),\;C:=(-1,0,0),\;D:=(0,1,0)$$

form a local optimal solution of Problem (1), but it is hard to prove that it is also a global maximum. The attempt for proving that $(A,B,C,D)$ is the unique critical point of $f:(S^{1})^{2}\times S^{2}_{\geq 0}\rightarrow R$ was not successful since too large objects occurred in the elimination process. We have also applied several numerical algorithms to search the optimal configuration and found from experiments that $4\sqrt{2}+4$ seems to be the real global maximum. In this paper, we devote ourselves to construct a proof of this fact by combining numerical and symbolic computation. Our strategy is as follows. In the first stage (the numerical global search stage) we prove that

In the second stage (the local critical analysis stage), we use symbolic computation to prove the following inequality:

Certainly, by combining Theorem 1 and Theorem 2 together, we get a complete solution to Problem (1). It is also clear that if we can construct larger neighborhoods in the local critical analysis stage, then the computation will be reduced significantly in the global numerical search stage, since $f(X)$ is changing very slowly when $X$ approaches critical points. The first work to use this two-stage method for proving geometric inequality can be traced to 1988 when Jingzhong Zhang of Chengdu Branch of the Chinese Academy of Sciences gave a machine proof (unpublished) on a Sharp PC-1500 pocket computer to a geometric inequality of Zirakzadeh [4], which says that given a triangle $ABC$, any points $P,Q,R$ on the boundary of $ABC$ which divide the perimeter of $ABC$ into three equal lengths satisfy $PQ+QR+RP\geq(AB+BC+CA)/2$. A detailed explanation of Zhang’s method is given in [5]. Related to the automated deduction in the local critical analysis stage, a general construction method for computing the size of the locally optimal regions of multivariable homogeneous polynomials is presented in [6]. Notice also that in [7] Hou et al. reported a solution for maximizing the distance sum between five points on the unit sphere essentially using the two-stage method.

For the sake of page limitation, we will concentrate mainly to make an explanation to the local critical analysis (stage 2) for Problem (1) in this paper. The paper is organized as follows. In Section 2 we transform Problem (1) to an equivalent non-linear optimization problem which has relatively simple objective function ${f}:(S^{1})^{2}\times D^{2}\rightarrow R$. In Section 3 we prove a stronger version of Theorem 2. In Section 4 we concisely describe the process of global numerical search for proving Theorem 1.

According to Lemma 1, we may assume that $A=(x_{0},y_{0},0)=(0,-1,0)$, $B=(x_{1},y_{1},0),C=(x_{2},y_{2},0)\in S^{1}$ and $D=(x_{3},y_{3},z_{3})\in S^{2}_{\geq 0}$ and search the maximal sum of the distances between the four points. It is clear that for any two points $P=(x,y,z),Q=(x^{\prime},y^{\prime},z^{\prime})\in S^{2}$ with $z\cdot z^{\prime}=0$, we have

$$PQ=d(P,Q)=\sqrt{(x-x^{\prime})^{2}+(y-y^{\prime})^{2}+(z-z^{\prime})^{2}}=\sqrt{2\cdot(1-x\,x^{\prime}-y\,y^{\prime})}.$$

Define the “warp distance” between two points $P_{1}=(x,y),Q_{1}=(x^{\prime},y^{\prime})$ in the unit disk $D^{2}$ as follows:

$$\delta(P_{1},Q_{1}):=\sqrt{2-2xx^{\prime}-2yy^{\prime}}.$$

Let

$$(\,)_{1}:{\mathbb{R}}^{3}\rightarrow{\mathbb{R}}^{2},\quad(x,y,z)\mapsto(x,y),$$

(5)

be the $z$-projection. Then for $A,B,C$ on the equator and $D$ on the hemisphere $S^{2}_{\geq 0}$, we have

$$d(P,Q)=\delta(P_{1},Q_{1})$$

for $P,Q\in\{A,B,C,D\}$. Thus, we can transform Problem (1) into the following optimization problem on $S^{1}\times S^{1}\times D^{2}$:

	$\displaystyle\max$		$\displaystyle\delta(A_{1},B_{1})+\delta(B_{1},C_{1})+\delta(C_{1},A_{1})+\delta(A_{1},D_{1})+\delta(B_{1},D_{1})+\delta(C_{1},D_{1}),$
	s.t.		$\displaystyle A_{1}=(0,-1),B_{1}=(x_{1},y_{1}),C_{1}=(x_{2},y_{2})\in S^{1}:=\{(x,y)|x^{2}+y^{2}=1\},$		(6)
			$\displaystyle D_{1}=(x_{3},y_{3})\in D^{2}=\{(x,y)\;|\;x^{2}+y^{2}\leq 1\}.$

It is clear that $\{A,B,C,D\}$ is an optimal configuration of Problem (1) if and only if $\{A_{1},B_{1},C_{1},D_{1}\}$ is an optimal configuration of Problem (2). We will prove the following result:

This result is stronger than Theorem 2, since if $A=(0,-1,0)$, and

$$B\in[\frac{31}{32},1]\times[-\frac{1}{4},\frac{1}{4}],C\in[-1,-\frac{31}{32}]\times[-\frac{1}{4},\frac{1}{4}],D\in[-\frac{1}{4},\frac{1}{4}]\times[\frac{31}{32},1]\times[0,\frac{1}{4}],$$

then their $z$-projections $A_{1},B_{1},C_{1},D_{1}$ satisfy the conditions (i), (ii) and (iii) in Theorem 3. To prove Theorem 3 we first setup a parametric representation for the coordinates of points $B_{1},C_{1},D_{1}$ in Problem (2). Notice that the property $O\in ABC$ in Lemma 1 implies that $x_{1}x_{2}<0$ so we may assume that

$$x_{1}=\frac{1-s^{2}}{1+s^{2}},\;y_{1}=\frac{2s}{1+s^{2}},\quad x_{2}=-\frac{1-t^{2}}{1+t^{2}},\;y_{2}=\frac{2t}{1+t^{2}},$$

for $-1\leq s,t\leq 1$, and since the optimal configuration $A,B,C,D$ satisfies

$$AD+BD+CD\geq 4+4\sqrt{2}-(AB+BC+CA)\geq 4+4\sqrt{2}-3\sqrt{3}>3\sqrt{2},$$

so without loss of generality, we may take $A=(0,-1,0)$ such that

$$AD=\sqrt{2+2y_{3}}=\max\{AD,BD,CD\}>\sqrt{2},$$

and therefore $y_{3}>0$, and we assumed that

$$x_{3}=\frac{2u}{1+u^{2}},\;y_{3}=\frac{1-v^{2}}{1+v^{2}},$$

for $-1\leq u\leq 1$ and $0\leq u\leq 1$. Furthermore, the condition $(x_{3},y_{3})\in D^{2}$ together with $v\geq 0$ implies that $-v\leq u\leq v$. Thus, the constraint conditions of Problem (2) can be expressed as

	$\displaystyle B_{1}=(\frac{1-s^{2}}{1+s^{2}},\frac{2s}{1+s^{2}}),C_{1}=(-\frac{1-t^{2}}{1+t^{2}},\frac{2t}{1+t^{2}}),D_{1}=(\frac{2u}{1+u^{2}},\;\frac{1-v^{2}}{1+v^{2}}),$
	$\displaystyle-1\leq s,t,u\leq 1,0\leq v\leq 1,-v\leq u\leq v.$

We also need the following two lemmas in the proof of Theorem 3.

Now we give the proof of Theorem 3.