MathLabs

第6問

整数 n>1n>1 と、平面上の nn 点からなる集合 SS を考える。SS の異なる2点間の距離はすべて少なくとも 11 とする。ある絶対定数 c>0c>0 に対して、SS を分離する直線 ℓ\ell で、SS の任意の点から ℓ\ell までの距離が少なくとも cn−1/3c n^{-1/3} となるものが存在することを証明せよ。（直線 ℓ\ell が点集合 SS を分離するとは、SS の2点を結ぶある線分が ℓ\ell と交わることである。）
ステップ 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 とすればよい。