P19 · L 形内的散点分离 · 讨论

本题n=8的最优值证明

NUE_13

分成三个1*1正方形容器,每个有4点在角落,其中有2点共享2个正方形(边缘中点),一点在中心共享3个正方形。由于每个小正方形最优距离均为1,因此总体最优值也为1。

SneakyZero

谢谢,这个角点构型说明 n=8 可以达到最小距离 1。现在缺的是反方向:任意八点构型都不能超过 1。你描述的公共角点和各小正方形中四点的分配,是这一个构型的性质;任意八点并不一定按这种方式分配,也不一定有某个单位正方形容纳四点。因此不能由各小正方形的四点最优值直接推出整体八点上界。暂不按这段论证标记已证明最优;可以继续尝试覆盖全部构型的分区直径上界。