用 n 个等圆盖住正方形 · n = 19
在边长为 1 的正方形里放 n 个点。取 r 为正方形里离所有点都最远的那个位置到最近的点的距离,把 r 压到最小。等价地说:用 n 个半径 r 的等圆盘盖住整块正方形,让 r 尽可能小。
子题n = 19
目标最小化 覆盖半径
已知最好(未证明)0.15784198174667375675Kari J. Nurmela and Patric R. J. Östergård 的构型收录于 Nurmela 与 Östergård(2000)的 HUT-TCS-A62 报告;论文当前最好值为 0.15784198174667375675,最优性未知。本站从论文矢量图与接触拓扑重建的九位坐标证书可严格验证到 0.157841982137137;它是参考答案,不是新的纪录。
已证明下界1/√(π·19)任何布局都不低于 0.129433967351735 · 当前纪录高出下界 21.9%面积下界:n 个半径 r 的圆盘至多盖住 nπr² 的面积,而正方形的面积是 1,所以 r ≥ 1/√(πn)。对每个 n 都成立,且不依赖任何未证明的猜想
严格定义
- 容器单位正方形,左下角是原点 (0, 0),右上角是 (1, 1),闭区间
- 提交恰好 n 个点的坐标,十进制小数,最多九位;两点不得重合
- 分数r(P) 是正方形上「到最近提交点的距离」的最大值。验证器精确求出它的平方,再精确开方并向上取整到 10⁻¹⁸。取整方向朝上,所以存下的数绝不会声称一个比实际更紧的覆盖
- 为何有限点在自己的最近邻辖区里就是最近点,而 |x − p|² 是凸的,凸多边形上的最大值必在顶点。于是对连续区域的搜索塌缩成有限个有理顶点的枚举,全程整数运算,不碰浮点
- 目标在所有合法点集 P 中让 r(P) 尽可能小