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。）
第 8/8 步：选择分离直线
上一步下一步
通俗地说

最大间隙给出所需分离线。

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

取最大投影间隙中点处的垂直平分线。它分离 SS，且每个点到它的距离至少为 δ/2≥(c′/2)n−1/3\delta/2\ge(c'/2)n^{-1/3}，取 c=c′/2c=c'/2 即得所需结论。