Problem 6

Consider an integer

n>1

, and a set

S

n

points in the plane such that the distance between any two different points in

S

is at least

1

. Prove there is a line

\ell

separating

S

such that the distance from any point of

S

\ell

is at least

c n^{-1/3}

for some absolute constant

c>0

. (A line

\ell

separates a set of points

S

if some segment joining two points in

S

crosses

\ell

Step 1 of 8: Choose the largest projection gap

Previous step Next step

In plain words

A projection gap immediately produces a separating line.

d(P,Q)\ge1\quad(P e Q),\qquad \delta=\max_{m}\max\{ ext{gap of consecutive projections onto }m\}

Detailed analysis

Let $\delta$ be the largest gap between consecutive projections when projecting onto any line $m$ . A gap of length $\delta$ gives a line perpendicular to $m$ through its midpoint that separates $S$ and keeps every point at distance at least $\delta/2$ .