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 8 of 8: Choose the separating line
Previous stepNext step
In plain words

The maximal gap supplies the desired separator.

d(S,ℓ)≥δ2≥c′2n−1/3d(S,\ell)\ge\frac\delta2\ge\frac{c'}2n^{-1/3}
Detailed analysis

Take the perpendicular bisector line through the midpoint of a largest projection gap. It separates SS and has point-distance at least δ/2≥(c′/2)n−1/3\delta/2\ge(c'/2)n^{-1/3}, giving the required bound with c=c′/2c=c'/2.