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。）
第 2/8 步：使用直径方向
上一步下一步
通俗地说

直径受最大投影间隙控制。

R=AB,R<(n−1)δ<nδR=AB,\qquad R<(n-1)\delta<n\delta
详细分析

取相距最远的点 A,BA,B，令 R=ABR=AB。在直线 ABAB 上，相邻投影间隔至多为 δ\delta，所以 R<(n−1)δ<nδR<(n-1)\delta<n\delta。