$n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil $ different distances between pairs of points

Question

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil $ different distances between pairs of points?

Answer 1

We show by a combinatorial argument that the number of distinct distances between pair of points is atleast $\displaystyle \left\lceil\frac{n-1}{3}\right\rceil$.

Let us denote by $\mathscr{P} = \{p_i: 1 \le i \le n\}$ the set of $n$ points in a plane with no $3$ points collinear and for each $p \in \mathscr{P}$, let $v_p$ be the number of distinct distances from $p$ to rest of the $n-1$ points.

Say, $\displaystyle \max_{p \in \mathscr{P}} v_p = v$.

Let, the distinct distances form a point $p_i$ to the remaining points be $\{d_j(p_i): 1\le j \le v_p \le v\}$.

Let, $\delta_{i,j}$ denote the number of points in $\mathscr{P}\setminus \{p_i\}$ that are at a distance of $d_j(p_i)$ from $p_i$, for $1 \le j \le v_{p_i}$.

Then, $$\sum\limits_{j=1}^{v_{p_i}} \delta_{i,j} = n-1 \tag{1}$$

for each $i = 1,2\cdots,n$.

Then, the number of pairs of points $(p_j,p_k)$ ($j \neq k$) from $\mathscr{P} \times \mathscr{P}$, such that they are equidistant from atleast one $p_i \in \mathscr{P}\setminus \{p_j,p_k\}$ is:

$$N = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{v_{p_i}} \binom{\delta_{i,j}}{2} \tag {2}$$

(Alternative combinatorial interpretation of $N$ is the number of isosceles triangles spanned by triples of points from $\mathscr{P}^3$, where equilateral triangles are counted with multiplicity $3$).

Clearly, $N$ attains minimum for a configuration $\mathscr{P}$ when for each point $p_i \in \mathscr{P}$, the values of $\displaystyle \binom{\delta_{i,j}}{2}$, for $1 \le j \le v_{p_i}$ are as nearly equal to each other as possible (due to the constraint $(1)$).

Thus, $$N \ge n\times v \times \binom{\frac{n-1}{v}}{2}\tag{3}$$

The other way to get $(3)$ is by an application of Cauchy-Schwarz Inequality:

$$\begin{align} N = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{v_{p_i}} \binom{\delta_{i,j}}{2} &= \frac{1}{2}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{v_{p_i}} (\delta_{i,j}^2 - \delta_{i,j}) \\&= \frac{1}{2}\sum\limits_{i=1}^{n}\left(\sum\limits_{j=1}^{v_{p_i}} \delta_{i,j}^2 - (n-1)\right) \\&\ge_{C.S.} \frac{1}{2}\sum\limits_{i=1}^{n}\left(\frac{1}{v_{p_i}}\left(\sum\limits_{j=1}^{v_{p_i}} \delta_{i,j}\right)^2 - (n-1)\right) \\&= \frac{1}{2}\sum\limits_{i=1}^{n}\left(\frac{1}{v_{p_i}}\left(n-1\right)^2 - (n-1)\right) \\& \ge \binom{n}{2}\left(\frac{n-1}{v} - 1\right)\end{align}$$

On the other hand since no $3$ points of $\mathscr{P}$ are collinear, each pair of points $(p_j,p_k)$ can be equidistant from at most $2$ other points.

Thus, $$N \le 2\binom{n}{2}$$

I.e., $$nv\binom{\frac{n-1}{v}}{2} \le N \le 2\binom{n}{2} \implies \frac{n-1}{v} < 3$$

Thus, $v$ the maximum number of distinct distance from a point $p \in \mathscr{P}$ to its neighbors is atleast $\displaystyle \left\lceil\frac{n-1}{3}\right\rceil$.

Note: The lower bound $\displaystyle \left\lceil \frac{n}{3}\right\rceil$ on the maximum number of distinct distances from a point to it's neighbors (and hence to the number of distinct distances between pair of points) for $n$ in a plane can be given if they are in convex position (i.e., if they form vertices of a convex polygon). This is only a particular case of the former no $3$ collinear case.