MathLabs

第6题

设整数 n>1n>1，平面上有一个含 nn 个点的集合 SS，且 SS 中任意两个不同点之间的距离至少为 11。证明存在一条分离 SS 的直线 ℓ\ell，使得对某个绝对常数 c>0c>0，SS 中每个点到 ℓ\ell 的距离至少为 cn−1/3c n^{-1/3}。（若连接 SS 中两点的某条线段与 ℓ\ell 相交，则称直线 ℓ\ell 分离点集 SS。）
第 1/8 步：选择最大投影间隙
上一步下一步
通俗地说

投影间隙立即产生分离直线。

d(P,Q)≥1(PeQ),δ=max⁡mmax⁡{extgapofconsecutiveprojectionsontom}d(P,Q)\ge1\quad(P e Q),\qquad \delta=\max_{m}\max\{ ext{gap of consecutive projections onto }m\}
详细分析

令 δ\delta 为投影到任意直线 mm 时相邻投影之间的最大间隙。取长度为 δ\delta 的间隙中点、垂直于 mm 的直线，它分离 SS，且每个点到它的距离至少为 δ/2\delta/2。