A problem on diameter of a set in Euclidean plane

Question

Let $S$ be a set of n points in a plane, where $n\geq2$. Suppose that $S$ has diameter $\Delta$. Prove that there are 2 points in $S$ that are separated by a distance at most $\frac{4\Delta}{\sqrt{n}}$.

Answer 1

Here is another answer, inspired by Sudipta Roy's comment on my other answer.

Pick any point; all points are contained in a circle of radius $\Delta$ around that point by definition.

Draw a circle of radius $\frac{2}{\sqrt{n}}\Delta$ Around each point. Then all of these circles are contained in a circle of radius $\Delta+\frac{2}{\sqrt{n}}\Delta=(1+\frac{2}{\sqrt{n}})\Delta$, which has area $\pi(1+\frac{2}{\sqrt{n}})^2\Delta^2$. If we have at least 16 points (if we have less than 16 the claim is immediate) then the area is at most $\pi(1+\frac{2}{\sqrt{16}})^2\Delta^2=\pi1.5^2\Delta^2=\pi2.25\Delta^2$.

Each of the circles covers an area of $\pi\left(\frac{2}{\sqrt{n}}\right)^2\Delta^2=\pi\cdot\frac{4}{n}\Delta^2$, so assuming for the sake of contradiction that no two of the circles intersect, they altogether cover an area of $4\pi\Delta^2>2.25\pi\Delta^2$, contradiction.

Therefore, two of the circles intersect. The radii of each of the circles is $\frac{2}{\sqrt{n}}\Delta$, so two of the points are within a distance of $\frac{4}{\sqrt{n}}$ of each other.

Answer 2

Lemma 1: There exists a circle of radius $\frac{\sqrt{2}}{2}\Delta$ containing all points in $S$.

Proof: Let the $x$-coordinate be the average of the minimum $x$-coordinate and the maximum $x$-coordinate, and let the $y$-coordinate be the average of the minimum $y$-coordinate and the maximum $y$-coordinate. Then the difference in the $x$-coordinate from this point to any point in $S$ is at most $\frac{1}{2}\Delta$, and the difference in the $y$-coordinate from this point to any point in $S$ is also at most $\frac{1}{2}\Delta$, so by Pythagoras, the maximum distance from this point to any point in $S$ is at most $\frac{\sqrt{2}}{2}\Delta.$ $\boxed{}$

Lemma 2: There exists a square of side length $\sqrt{2}\Delta$ containing all points in $S$.

Proof: A circle of radius $\frac{\sqrt{2}}{2}\Delta$ is contained in the square of side length $\sqrt{2}\Delta$ centered at its center. $\boxed{}$

So now we have a square of side length $\sqrt{2}\Delta$ containing all points in $S$. Cut it up by drawing $\lfloor\sqrt{n-1}\rfloor-1$ vertical lines equally spaced from the left edge to the right edge (making $\lfloor\sqrt{n-1}\rfloor$ columns) and $\lfloor\sqrt{n-1}\rfloor-1$ horizontal lines equally spaced from the top edge to the bottom edge (making $\lfloor\sqrt{n-1}\rfloor$ rows). Altogether, this cuts it up into at most $\lfloor\sqrt{n-1}\rfloor\cdot\lfloor\sqrt{n-1}\rfloor\leq n-1$ squares of side length $\frac{\sqrt{2}}{\lfloor\sqrt{n-1}\rfloor}\Delta$.

By the pigeonhole principle, at least two dots from $S$ must be in the same square, and the largest distance between two points in a square of side length $\frac{\sqrt{2}}{\lfloor\sqrt{n-1}\rfloor}\Delta$ is $\frac{\sqrt{2}}{\lfloor\sqrt{n-1}\rfloor}\Delta\cdot\sqrt{2}=\frac{2}{\lfloor\sqrt{n-1}\rfloor}\Delta$.

So far, we have two points separated by a distance at most $\frac{2}{\lfloor\sqrt{n-1}\rfloor}\Delta$, so it suffices to show that $\frac{2}{\lfloor\sqrt{n-1}\rfloor}\Delta\leq \frac{4}{\sqrt{n}}\Delta$, and because $2\Delta$ is positive, this is equivalent to showing that $\frac{1}{\lfloor\sqrt{n-1}\rfloor}\leq \frac{2}{\sqrt{n}}$ for $n>16$ (for $n\leq16$, the statement you want to prove is immediate because $\frac{4}{\sqrt{n}}\leq1$, so $\frac{4}{\sqrt{n}}\Delta\leq\Delta$, so you can pick any two points).

Algebra Section

$$\frac{1}{\lfloor\sqrt{n-1}\rfloor}\leq\frac{1}{\sqrt{n-1}-1},$$

so we it suffices to show that

$$\frac{1}{\sqrt{n-1}-1}\leq\frac{2}{\sqrt{n}}$$

which is equivalent to

$$\sqrt{n}\leq2(\sqrt{n-1}-1)$$

Both sides are positive, so we can square both sides, so it suffices to show that

$$n\leq4(\sqrt{n-1}-1)^2=4(n-1-2\sqrt{n-1}+1)=4n-8\sqrt{n-1}$$

which is equivalent to

$$3n\geq8\sqrt{n-1}.$$

Squaring gives

$$9n^2\geq64n-64$$

which, by the quadratic formula, is true for $n>\frac{64+16\sqrt{7}}{18}\approx5.9<16$, so we are done.