# Sum of squared nearest-neighbor distances between points in a square

Let $$\square_2=\{(x,y): 0\leq x, y\leq1\}$$ be the unit square in $$\mathbb{R}^2$$. Take $$n>1$$ points $$P_1, \dots, P_n\in\square_2$$.

Denote the distances $$d_j=\min\{\Vert P_k-P_j\Vert: k\neq j\}$$, for $$j=1,\dots, n$$.

QUESTION. Is it true that $$d_1^2+\cdots+d_n^2\leq 4$$? The bound is tight when $$n=2$$.

• ...and tight when $n= 4$ (points at corners). – David G. Stork Jan 16 '19 at 19:43
• A close result: any $n$ points in a right triangle $ABC$, $\angle ABC=\pi/2$, may be enumerated by $P_1,\dots,P_n$ so that $AP_1^2+P_1P_2^2+\dots+P_{n-1}P_n^2+P_nC^2\leqslant AB^2$. The proof is similar to Iosif Pinelis's idea: take a height $BH$ and apply the induction proposition to triangles $AHB,CHB$ (if all point lie in the same triangle, proceed partitioning.) – Fedor Petrov Jan 16 '19 at 20:17
• Perhaps this answer by @achillehui will help: Average distance between $n$ randomly distributed points on a square with their nearest neighbors. – Joseph O'Rourke Jan 17 '19 at 0:11

We shall prove the more general result: for $$n\ge2$$ distinct points and any positive real $$a,b$$, we have $$D(R):=d_1^2+\cdots+d_n^2\le 2a^2+2b^2$$, where the points $$P_j$$ are now in an $$a\times b$$ rectangle $$R$$ and the distances $$d_j$$ are defined as in the OP. Let us use induction on $$n$$. For $$n=2$$, the result is obvious. Suppose now that $$n>2$$. Without loss of generality (wlog), $$R=[0,a]\times[0,b]$$. "Partition" $$R$$ into the four $$\frac a2\times \frac b2$$ rectangles $$R_1:=[0,\frac a2]\times[0,\frac b2],R_2:=[\frac a2,a]\times[0,\frac b2], R_3:=[0,\frac a2]\times[\frac b2,b],R_4:=[\frac a2,a]\times[\frac b2,b]$$

Let $$n_1,\dots,n_4$$ be the numbers of the points in the rectangles $$R_1,\dots,R_4$$, respectively.

Case 1: $$n_1,\dots,n_4\ge2$$. Then, by induction, $$$$d_1^2+\cdots+d_n^2=D(R)\le D(R_1)+\dots+D(R_4)\le4[2(\tfrac a2)^2+2(\tfrac b2)^2]= 2a^2+2b^2.$$$$

Lemma 1. Suppose that $$n_1\ge2$$ and $$n_2=1$$, so that there is exactly one point, say $$Q$$, in $$R_2$$. Then $$$$D(R_1)+d(Q,R_1)^2\le a^2+b^2,$$$$ where $$d(Q,R_1)$$ is the shortest distance from $$Q$$ to the $$n_1$$ points in $$R_1$$.

Proof: Let $$s$$ be the largest abscissa of all the $$n_1$$ points in $$R_1$$, so that $$0\le s\le\tfrac a2$$. Let $$(u,v):=Q$$, so that $$\tfrac a2\le u\le a$$ and $$0\le v\le\tfrac b2$$. By symmetry, wlog $$0\le v\le\tfrac b4$$, and hence $$d(Q,R_1)^2\le(u-s)^2+(\tfrac b2-v)^2$$. So, by induction, $$$$D(R_1)+d(Q,R_1)^2\le2s^2+2(\tfrac b2)^2+(u-s)^2+(\tfrac b2-v)^2\le a^2+b^2,$$$$ which proves Lemma 1. $$\Box$$

Case 2: One of the $$n_j$$'s is $$1$$, and the other $$n_j$$'s are $$\ge2$$. Here wlog $$n_1,n_3,n_4\ge2$$ and $$n_2=1$$. Then, in view of Lemma 1, $$$$d_1^2+\cdots+d_n^2=D(R)\le D(R_1)+d(Q,R_1)^2+D(R_3)+D(R_4)\le a^2+b^2+2[2(\tfrac a2)^2+2(\tfrac b2)^2]= 2a^2+2b^2.$$$$

Case 3: Two of the $$n_j$$'s are $$1$$'s, and the other $$n_j$$'s are $$\ge2$$. Here wlog $$n_1,n_3\ge2$$ and $$n_2=n_4=1$$ (the "adjacent" subcase) or $$n_1,n_4\ge2$$ and $$n_2=n_3=1$$ (the "non-adjacent" subcase). In the "adjacent" subcase, let $$Q$$ be the only point in $$R_2$$, and let $$T$$ be the only point in $$R_4$$. Then, in view of Lemma 1, $$$$d_1^2+\cdots+d_n^2=D(R)\le D(R_1)+d(Q,R_1)^2+D(R_3)+d(T,R_3)^2\le a^2+b^2+a^2+b^2= 2a^2+2b^2.$$$$ The "non-adjacent" subcase is considered quite similarly, by using an appropriate flip/symmetry.

Case 4: Three of the $$n_j$$'s are $$1$$'s, and the other $$n_j$$ is $$\ge2$$. Here wlog $$n_1\ge2$$ and $$n_2=n_3=n_4=1$$. Let $$Q_2=(p,q),Q_3=(u,v),Q_4=(x,y)$$ be the unique points in $$R_2,R_3,R_4$$, respectively, so that $$p,x\in[\tfrac a2,a]$$, $$v,y\in[\tfrac b2,b]$$, $$u\in[0,\tfrac a2]$$, $$q\in[0,\tfrac b2]$$.

Let $$s$$ and $$t$$ be, respectively, the largest abscissa and ordinate of all the $$n_1$$ points in $$R_1$$. Then
$$\begin{multline} D(R)\le B:=D(R_1)+d(Q_2,S)^2+d(Q_3,T)^2+\frac{\|Q_4-Q_2\|^2+\|Q_4-Q_3\|^2}2, \end{multline}$$ where $$S$$ is a point (among the $$n_1$$ points in $$R_1$$) with the largest abscissa $$s$$, and $$T$$ is a point (among the $$n_1$$ points in $$R_1$$) with the largest ordinate $$t$$, so that $$S=(s,\eta)$$ for some $$\eta\in[0,t]$$, and $$T=(\xi,t)$$ for some $$\xi\in[0,s]$$. Of course, $$d(Q_2,S)$$ is a convex function of $$\eta\in[0,t]$$, and so, $$$$d(Q_2,S)^2\le\max(d(Q_2,(s,0))^2,d(Q_2,(s,t))^2) =(p - s)^2 + \max(q^2, (q-t)^2).$$$$ Similarly, $$$$d(Q_3,T)^2\le \max(u^2, (u-s)^2) + (v - t)^2.$$$$ Next, $$$$\|Q_4-Q_2\|^2+\|Q_4-Q_3\|^2=(x - p)^2 + (y - q)^2 + (x - u)^2 + (y - v)^2,$$$$ which is convex in $$x,y$$, with the maximum in $$x\in[\tfrac a2,a]$$ and $$y\in[\tfrac b2,b]$$ attained at $$x=a$$ and $$y=b$$, for any given $$p\in[\tfrac a2,a]$$, $$v\in[\tfrac b2,b]$$, $$u\in[0,\tfrac a2]$$, $$q\in[0,\tfrac b2]$$. Further, by induction, $$D(R_1)\le2s^2+2t^2$$. Thus, $$\begin{multline} D(R)\le B\le B_1:= 2 s^2+2t^2+\max \left(q^2,(q-t)^2\right)+\max \left((u-s)^2,u^2\right) \\ +(p-s)^2+(v-t)^2 \\ +\tfrac{1}{2} \left((a-p)^2+(b-q)^2\right)+\tfrac{1}{2} \left((a-u)^2+(b-v)^2\right). \end{multline}$$ Clearly, $$B_1$$ is convex in $$p,v$$, and one can see that the maximum of $$B_1$$ in $$p\in[\tfrac a2,a]$$ and $$v\in[\tfrac b2,b]$$ is attained at $$p=a$$ and $$v=b$$, for any given $$s\in[0,\tfrac a2]$$, $$t\in[0,\tfrac b2]$$, $$u\in[0,\tfrac a2]$$, $$q\in[0,\tfrac b2]$$. So, $$$$B_1\le B_{21}+B_{22}+B_{23},$$$$ where \begin{align} B_{21}&:=\max \left(q^2,(q-t)^2\right)- b q+q^2/2, \\ B_{22}&:=\max \left(u^2,(u-s)^2\right)- a u+u^2/2, \\ B_{23}&:=\tfrac{1}{2} \left(3 a^2+3 b^2-4 a s-4 b t+6 \left(s^2+t^2\right)\right). \end{align} Next, $$$$B_{21}\le t^2,\quad B_{22}\le s^2$$$$ for $$q,t\in[0,\tfrac b2]$$ and $$u,s\in[0,\tfrac a2]$$. So, $$$$D(R)\le B\le B_1\le B_{21}+B_{22}+B_{23} \le\tfrac{1}{2} (3 a^2 + 3 b^2) -4 (\tfrac a2 - s) s - 4 (\tfrac b2 - t) t \le\tfrac{1}{2} (3 a^2 + 3 b^2)\le2 a^2 + 2 b^2.$$$$

Case 5: This case obtains from Cases 2, 3, 4 by replacing there some of the conditions of the form $$n_j=1$$ by $$n_j=0$$. This case immediately follows from Cases 2, 3, 4, because now the nonnegative contributions of the single points will be replaced by $$0$$ --- with the only exception occurring when three of the $$n_j$$'s are $$0$$ and hence the remaining one of the $$n_j$$'s (say $$n_1$$) equals $$n$$. Indeed, in the latter exceptional subcase, we cannot use the induction, since $$n_1=n\not. The remedy in this case is to continue the "partitioning" of the smaller rectangles containing all the $$n$$ points until we no longer have such an exceptional situation. This process will stop. Indeed, if it never stops, then all the $$n$$ distinct points will get eventually contained in a singleton set, which is a contradiction.

So far, we have consider all the cases when at least one of the $$n_j$$'s is $$\ge2$$. Otherwise, we have $$n_j\le1$$ for all $$j=1,\dots,4$$ and hence $$n\le4$$. Since $$n>2$$, it remains to consider the following two cases.

Case 6: $$n=3$$. By shrinking the rectangle $$R$$, wlog we may assume that each side of $$R$$ contains at least one of the three points $$P_1,P_2,P_3$$. By the pigeonhole principle, at least two sides of the rectangle must share one of the three points. Also, wlog none of the points $$P_1,P_2,P_3$$ is in the interior of $$R$$. Indeed, if e.g. $$P_3$$ is in the interior of $$R$$, then we can move $$P_3$$ away from the line $$\ell(P_1,P_2)$$ (through $$P_1,P_2$$) in the direction perpendicular to $$\ell(P_1,P_2)$$ (till we hit the boundary of $$R$$), so that all the pairwise distances between the points $$P_1,P_2,P_3$$ may only increase, and then $$D(R)$$ may only increase.

So, wlog $$P_1=(0,0),P_2=(u,b),P_3=(a,v)$$ for some $$u\in[0,a]$$ and $$v\in[0,b]$$. So, $$$$D(R)\le B_3:=\frac{P_1P_2^2+P_1P_3^2}2+\frac{P_2P_1^2+P_2P_3^2}2+\frac{P_3P_2^2+P_3P_1^2}2= P_1P_2^2+P_1P_3^2+P_2P_3^2,$$$$ where $$AB:=\|A-B\|$$. Since $$B_3$$ is convex in $$u,v$$, its maximum in $$u\in[0,a]$$ and $$v\in[0,b]$$ is attained when $$u\in\{0,a\}$$ and $$v\in\{0,b\}$$, and this maximum is $$2a^2+2b^2$$, which proves Case 6.

Case 7: $$n=4$$. Again, by shrinking the rectangle $$R$$, wlog we may assume that each side of $$R$$ contains at least one of the four points $$P_1,P_2,P_3,P_4$$. Also, each of the four points is either (i) in the convex hull of the other three points or (ii) on the boundary of $$R$$. Indeed, otherwise wlog $$P_4$$ is in the interior of $$R$$, but not in the convex hull of $$P_1,P_2,P_3$$; more specifically, we may assume that the points $$P_4$$ and $$P_3$$ are to the opposite sides of the line $$\ell(P_1,P_2)$$. Then we can move $$P_4$$ away from the triangle $$P_1P_2P_3$$ in the direction perpendicular to the line $$\ell(P_1,P_2)$$ (till we hit the boundary of $$R$$), so that all the pairwise distances between the points $$P_1,P_2,P_3,P_4$$ may only increase, and then $$D(R)$$ may only increase. Therefore, wlog we have one the following subcases.

Subcase 7.1: $$P_4$$ is in the convex hull of $$P_1,P_2,P_3$$, so that $$P_4=(1-s-t)P_1+sP_2+tP_3$$ for some $$s,t$$ such that $$s,t\ge0$$ and $$s+t\le1$$. Also, here, as in Case 6, wlog $$P_1=(0,0),P_2=(u,b),P_3=(a,v)$$ for some $$u\in[0,a]$$ and $$v\in[0,b]$$. Hence $$$$D(R)\le B_{71}:=P_1P_4^2+P_2P_4^2+P_3P_4^2+[(1-s-t)P_4P_1^2+s\,P_4P_2^2+t\,P_4P_3^2]\le2a^2+2b^2;$$$$ the latter inequality follows easily by the convexity of $$B_{71}$$ in each of the variables $$u,v,(s,t)$$. Thus, Subcase 7.1 is done.

Subcase 7.2: All the four points $$P_1,P_2,P_3,P_4$$ are on the boundary of $$R$$.

Subsubcase 7.2.1: There is a bijection $$\beta$$ from the set of the points $$\{P_1,P_2,P_3,P_4\}$$ to the set of the sides of $$R$$ such that $$P_j\in\beta(P_j)$$ for all $$j$$. So, wlog $$P_1=(s,0),P_2=(0,t),P_3=(u,b),P_4=(a,v)$$ for some $$s,u\in[0,a]$$ and $$t,v\in[0,b]$$. Then, similarly to the case $$n=3$$,
$$$$D(R)\le\frac{P_1P_2^2+P_1P_4^2}2+\frac{P_2P_1^2+P_2P_3^2}2 +\frac{P_3P_2^2+P_3P_4^2}2+\frac{P_4P_1^2+P_4P_3^2}2\le2a^2+2b^2,$$$$ by convexity. Subcase 7.2.1 is done.

Subsubcase 7.2.2: One of the points $$P_1,P_2,P_3,P_4$$ (say $$P_1$$) is shared by two sides of the rectangle $$R$$. So, wlog $$P_1=(0,0)$$. Suppose that one of the two sides of $$R$$ (say $$S_1$$ and $$S_2$$) sharing the point $$P_1$$ contains one of the points $$P_2,P_3,P_4$$; let us say this side is $$S_1$$. Then we can move $$P_1$$ slightly along the side $$S_2$$ out of its position at $$(0,0)$$. In view of the continuity of $$D(R)$$ in $$P_1$$, we can thus get rid of the sharing -- provided that at least one of the two sides of $$R$$ sharing the point $$P_1$$ contains one of the points $$P_2,P_3,P_4$$. So, wlog $$P_1=(0,0)$$ and none of the two sides of $$R$$ sharing the point $$P_1$$ contains any of the points $$P_2,P_3,P_4$$. So, one of the sides of $$R$$ not sharing the point $$P_1$$ contains two of the points $$P_2,P_3,P_4$$. Therefore and by the interchangeability of the horizontal and vertical directions, wlog $$P_1=(0,0),P_2=(u,b),P_3=(a,v),P_4=(a,w)$$ for some $$u\in[0,a]$$ and $$v,w\in[0,b]$$ such that $$v>w$$. So,
$$$$D(R)\le P_1P_2^2+P_2P_3^2+P_3P_4^2+P_4P_1^2\le2a^2+2b^2,$$$$ again by convexity. Subcase 7.2.2 is done, as well as the entire proof of the bound $$2a^2+2b^2$$.

• I have now considered more cases and simplified the proof, by introducing Lemma 1. – Iosif Pinelis Jan 17 '19 at 3:13
• It might be useful to note that there's still one case left - when 3 are 1s. – user44191 Jan 17 '19 at 3:42
• I have now added yet another case, which appears to be the most difficult one. – Iosif Pinelis Jan 17 '19 at 21:33
• One (hopefully) comparatively small step remains to finish the proof. – Iosif Pinelis Jan 17 '19 at 21:59
• The proof is finally completely done. – Iosif Pinelis Jan 21 '19 at 2:06

You draw the discs $$D_j$$ of radius $$d_j/2$$ and center $$P_j$$. Then because $$\|P_j-P_k\|\geq \frac{1}{2}(d_j+d_k)$$ the discs are disjoint and we have $$\sum \pi\frac{d_j^2}{4}\leq 1+\mathcal{A}$$where $$\mathcal{A}$$ is the surface covered by the discs outside $$\square_2$$. So this give an elementary proof if all $$d_j$$ are smaller than $$\sqrt{\pi}-1\approx 0,77$$ since $$(1+\mathcal{A})\leq (1+\max_j d_j)^2$$.