P52 · 极值构型 · 经典问题

最远与最近距离之比

1y0
0x1
已验证构造最远与最近的一对点
n = 12当前纪录 · 打开子题

在平面上放置 n 个点,记最远两点距离为 D、最近两点距离为 d,使比值 D/d 尽可能小。

严格定义

  • 容器没有真正的容器:比值不随缩放平移改变,答案缩放到单位正方形内写下即可
  • 提交恰好 n 个点 points,两两不重合
  • 目标让 D/d 尽可能小。内部以平方比精确比较

帮助理解

哪里有优化空间

既要最近的不太近、又要最远的不太远,点集被迫又圆又匀:内部像六边形蜂窝,输赢却决定在边界的取舍。

前沿在哪里

这一族收录在 Friedman 的 maxmin 页(Rechenberg、Cantrell、Audet 等人的构造),全部未证明;本站已录三个值,其余 n 未录,开放。

查看来源
逐个 n 竞争

所有 n 的当前最佳解

每个 n 都是一道独立的子题,各有各的纪录和页面。选择任意一格查看当前构造,或提交更好的答案。

n9
当前纪录2.683281573
纪录保持者NUE_13
解题方式人工
查看题目
n10
当前纪录2.952567023
纪录保持者NUE_13
解题方式人工
查看题目
n11
当前纪录3.605551276
纪录保持者创始基准
解题方式人工
查看题目
n12
当前纪录2.909312918已知最好 2.909312912
纪录保持者创始基准
解题方式人工
查看题目
n13
当前纪录4.242640688
纪录保持者创始基准
解题方式人工
查看题目
n14
当前纪录4.242640688
纪录保持者创始基准
解题方式人工
查看题目
n15
当前纪录4.242640688
纪录保持者创始基准
解题方式人工
查看题目
n16
当前纪录3.590157373已知最好 3.590157366
纪录保持者创始基准
解题方式人工
查看题目
n17
当前纪录5
纪录保持者创始基准
解题方式人工
查看题目
n18
当前纪录5
纪录保持者创始基准
解题方式人工
查看题目
n19
当前纪录3.863703315已知最好 3.863703306
纪录保持者创始基准
解题方式人工
查看题目
n20
当前纪录5
纪录保持者创始基准
解题方式人工
查看题目
n21
当前纪录5.65685425
纪录保持者创始基准
解题方式人工
查看题目
n22
当前纪录5.65685425
纪录保持者创始基准
解题方式人工
查看题目
n23
当前纪录5.65685425
纪录保持者创始基准
解题方式人工
查看题目
n24
当前纪录5.65685425已知最好 4.574735319
纪录保持者创始基准
解题方式人工
查看题目
n25
当前纪录5.65685425
纪录保持者创始基准
解题方式人工
查看题目
n26
当前纪录6.403124238
纪录保持者创始基准
解题方式人工
查看题目
n27
当前纪录6.403124238
纪录保持者创始基准
解题方式人工
查看题目
n28
当前纪录6.403124238
纪录保持者创始基准
解题方式人工
查看题目