P73 · 极值构型 · 经典问题 · 难

用 n 个等圆盖住正方形 · n = 23

在边长为 1 的正方形里放 n 个点。取 r 为正方形里离所有点都最远的那个位置到最近的点的距离,把 r 压到最小。等价地说:用 n 个半径 r 的等圆盘盖住整块正方形,让 r 尽可能小。

子题n = 23
目标最小化 覆盖半径
已证明下界1/√(π·23)任何布局都不低于 0.117641660430565 · 当前纪录高出下界 20.1%面积下界:n 个半径 r 的圆盘至多盖住 nπr² 的面积,而正方形的面积是 1,所以 r ≥ 1/√(πn)。对每个 n 都成立,且不依赖任何未证明的猜想

严格定义

  • 容器单位正方形,左下角是原点 (0, 0),右上角是 (1, 1),闭区间
  • 提交恰好 n 个点的坐标,十进制小数,最多九位;两点不得重合
  • 分数r(P) 是正方形上「到最近提交点的距离」的最大值。验证器精确求出它的平方,再精确开方并向上取整到 10⁻¹⁸。取整方向朝上,所以存下的数绝不会声称一个比实际更紧的覆盖r(P)=maxxKminixpi
  • 为何有限点在自己的最近邻辖区里就是最近点,而 |x − p|² 是凸的,凸多边形上的最大值必在顶点。于是对连续区域的搜索塌缩成有限个有理顶点的枚举,全程整数运算,不碰浮点
  • 目标在所有合法点集 P 中让 r(P) 尽可能小minPr(P)
放大来摆,然后提交
1y0
0x1
已验证构造23 个等圆盘,共同半径 0.141245;标出的那一点是最难够到的位置,半径由它决定

帮助理解

它和填充正好相反

填充禁止重叠,圆会往里缩、躲开边界;覆盖允许重叠,反而必须把圆压进四个角。同样的 n,好的覆盖和好的填充长得完全不一样。

前沿在哪里

网格不是最优解。无限平面上的最优覆盖由 Kershner 在 1939 年解决(正六边形最省),但有边界的正方形会出现完全不同的角落效应。n = 5 与 n = 7 已证明最优;n = 6、8–30 展示的是公开文献中的当前最好构型,仍可能被改进。本站已把 HUT-TCS-A62 的矢量图逐一重建为可验证坐标。n = 31–35 可以挑战,但在找到可公开复现的文献构型前,不冒充已有 SOTA。

查看来源
用 n 个等圆盖住正方形 n = 23 的当前纪录构型,0.141244822774814
当前第一名

0.141244822774814

覆盖半径

答案来源A. Lengyel and I. A. Veres; independently Kari J. Nurmela and Patric R. J. Östergård
解题方式公开参考构造
挑战这个纪录
ANSWER FORMAT

答案怎么写

容器是边长 1 的正方形:左下角是原点 (0, 0),右上角是 (1, 1)。你交的是 n 个圆心;半径不用你写,它就是「最难够到的那个位置离最近圆心的距离」,也就是你的分数。坐标写成小数,例如 "0.25",最多九位小数。

提交 points。每个坐标写成十进制字符串,例如 "0.25",最多九位小数。分数是盖住整块正方形所需的共同半径,越小越好。

当前第一名的答案

{
  "points": [
    [
      "0.718991367",
      "0.089467605"
    ],
    [
      "0.374222628",
      "0.705511074"
    ],
    [
      "0.500000005",
      "0.499999997"
    ],
    [
      "0.914143745",
      "0.887844736"
    ],
    [
      "0.625777378",
      "0.705511079"
    ],
    [
      "0.499999975",
      "0.911022155"
    ],
    [
      "0.085856233",
      "0.887844719"
    ],
    [
      "0.085856239",
      "0.112155277"
    ],
    [
      "0.718991347",
      "0.910532392"
    ],
    [
      "0.248445253",
      "0.499999995"
    ],
    [
      "0.281008625",
      "0.089467604"
    ],
    [
      "0.751554758",
      "0.500000009"
    ],
    [
      "1.000000000",
      "0.500000004"
    ],
    [
      "0.875777380",
      "0.708467149"
    ],
    [
      "0.914143757",
      "0.112155273"
    ],
    [
      "0.499999996",
      "0.088977848"
    ],
    [
      "0.374222629",
      "0.294488918"
    ],
    [
      "0.281008606",
      "0.910532389"
    ],
    [
      "0.124222627",
      "0.291532862"
    ],
    [
      "0.124222626",
      "0.708467126"
    ],
    [
      "0.875777378",
      "0.291532864"
    ],
    [
      "0.000000000",
      "0.499999993"
    ],
    [
      "0.625777384",
      "0.294488927"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看

子题参数

{
  "n": 23
}

当前第一名的答案

{
  "points": [
    [
      "0.718991367",
      "0.089467605"
    ],
    [
      "0.374222628",
      "0.705511074"
    ],
    [
      "0.500000005",
      "0.499999997"
    ],
    [
      "0.914143745",
      "0.887844736"
    ],
    [
      "0.625777378",
      "0.705511079"
    ],
    [
      "0.499999975",
      "0.911022155"
    ],
    [
      "0.085856233",
      "0.887844719"
    ],
    [
      "0.085856239",
      "0.112155277"
    ],
    [
      "0.718991347",
      "0.910532392"
    ],
    [
      "0.248445253",
      "0.499999995"
    ],
    [
      "0.281008625",
      "0.089467604"
    ],
    [
      "0.751554758",
      "0.500000009"
    ],
    [
      "1.000000000",
      "0.500000004"
    ],
    [
      "0.875777380",
      "0.708467149"
    ],
    [
      "0.914143757",
      "0.112155273"
    ],
    [
      "0.499999996",
      "0.088977848"
    ],
    [
      "0.374222629",
      "0.294488918"
    ],
    [
      "0.281008606",
      "0.910532389"
    ],
    [
      "0.124222627",
      "0.291532862"
    ],
    [
      "0.124222626",
      "0.708467126"
    ],
    [
      "0.875777378",
      "0.291532864"
    ],
    [
      "0.000000000",
      "0.499999993"
    ],
    [
      "0.625777384",
      "0.294488927"
    ]
  ]
}

提交 points。每个坐标写成十进制字符串,例如 "0.25",最多九位小数。分数是盖住整块正方形所需的共同半径,越小越好。 · 验证器 v1.0.0

DISCUSSION

讨论区

聊思路、贴方法、问为什么卡住。发帖即公开署名,与纪录同一个名字;署名后的 #编号是账号的注册序号,冒不了名。发言资格与实绩绑定:破过一次纪录,就永久拥有发言权。新发言经自动审核后公开。

还没有帖子。第一个聊聊这道题的思路?