MathLabs

Problem 6

Consider an integer n>1n>1, and a set SS of nn points in the plane such that the distance between any two different points in SS is at least 11. Prove there is a line ℓ\ell separating SS such that the distance from any point of SS to ℓ\ell is at least cn−1/3c n^{-1/3} for some absolute constant c>0c>0. (A line ℓ\ell separates a set of points SS if some segment joining two points in SS crosses ℓ\ell.)
Step 2 of 8: Use a diameter direction
Previous stepNext step
In plain words

The diameter is controlled by the largest projection gap.

R=AB,R<(n−1)δ<nδR=AB,\qquad R<(n-1)\delta<n\delta
Detailed analysis

Choose farthest points A,BA,B and put R=ABR=AB. On the line ABAB, consecutive projections are at most δ\delta apart, so R<(n−1)δ<nδR<(n-1)\delta<n\delta.