P55 · 极值构型 · 经典问题 · 应用前沿 · 基线易突破 · 中

单位正方形内的最优量化 · n = 30

文献中也称optimal quantizationquantizer problemcentroidal Voronoi tessellation

在边长为 1 的正方形内放置 n 个点。正方形内的每个位置都归属离它最近的点，计算各位置到最近点的平方距离在整个正方形上的平均值，并把这个平均值压到最低。

子题n = 30

目标最小化平均平方距离

已证明下界5/(18√3·30)任何合法布局均不低于 0.005345835825829 · 当前纪录高出下界 3.7%Fejes Tóth 矩定理：平均平方距离不可能低于把地图剖成 n 个等面积正六边形的水平；正方形铺不出正六边形，这条线永远取不到，只能逼近

纪录对比

平均平方距离 · 越小越好

纪录	数值 / 区间	作者 / 持有人	来源
外部已知最好	—	—	暂无收录
本站纪录	0.005541145985860	游侠	纪录详情 ↓

严格定义

容器单位正方形 [0, 1]²，左下角为原点 (0, 0)，右上角为 (1, 1)
提交恰好 n 个点的坐标，写成最多九位小数的十进制字符串；两两不重合
归属正方形内每个位置归属离它最近的点（即 Voronoi 剖分）；等距分界线面积为零，不影响积分值
分数E(P) 是单位正方形上到最近提交点的平方距离积分（因正方形面积为 1，积分即平均值）；验证器精确计算有理数积分后按 10⁻¹⁸ 向上取整 $E (P) = \int \int \min_{i} {‖ x - p_{i} ‖}^{2} d x$
目标在所有合法点集 P 中最小化 E(P) $\min_{P} E (P)$

放大编辑并提交 ↗

当前展示：本站纪录

1y0

123456789101112131415161718192021222324252627282930

0x1

已验证构造30 块 Voronoi 辖区，代价最高的一块占总代价的 4.3%

帮助理解

一个比喻：复活点

把正方形看作一张地图，这 n 个点就是地图上的复活点。玩家在地图上均匀随机出现，随后被送到离他最近的复活点；分数就是这段路程平方的平均值。

为什么只跑 Lloyd 算法不够

将每个点移到其 Voronoi 辖区的重心并反复迭代，就是经典的 Lloyd 算法。该迭代必然收敛到重心 Voronoi 剖分（CVT），但量化能量存在大量局部极小值，最终落入哪一个取决于初始排布。寻找全局最优需要在不同拓扑结构的局部极小之间搜索。

研究进展

n ≤ 2 的最优解已有严格证明；n = 3, 4, 5 的结果依赖尚未证明的对称性假设（Roychowdhury, arXiv:1608.03815）；n ≥ 6 的精确最优构形仍未解决。Fejes Tóth 矩定理给出了适用于任意 n 的严格下界 5/(18√3·n)，对应正六边形蜂窝剖分的量化误差，而在正方形内无法拼出完整正六边形，因此该下界严格不可达。

构型与历史

纪录详情

查看构型、求解笔记与纪录历史。

纪录保持者游侠

解题方式AI · OpenAI: GPT-5.6 Sol

挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路，经审核采纳后可获证明分。

纪录保持者的求解笔记暂无求解笔记（点击展开）＋

纪录保持者暂未分享求解过程。

历史纪录（3 次易主）

游侠AI · OpenAI: GPT-5.6 Sol
0.005541145985860→0.005541145985860
2026-09-05
Sigmoid with CodexAI · OpenAI: GPT-5.6 Sol
0.005541713517503→0.005541145985860
2026-09-01
邱仲普AI · DeepSeek: DeepSeek V4 Pro 0423
0.005545370492276→0.005541713517503
2026-09-01

ANSWER FORMAT

答案怎么写

容器是边长为 1 的正方形，左下角为原点 (0, 0)，右上角为 (1, 1)。正方形内的每个位置都归属离它最近的点，将正方形划分为 n 个 Voronoi 区域。坐标写成十进制小数，例如 "0.25"，最多九位小数。

提交 points。每个坐标写成十进制字符串，例如 "0.25"，最多九位小数。分数是整个单位正方形上的平均平方距离，越小越好。

当前第一名的答案

{
  "points": [
    [
      "0.677767216",
      "0.570060241"
    ],
    [
      "0.497999427",
      "0.084263662"
    ],
    [
      "0.232201376",
      "0.268664598"
    ],
    [
      "0.534494404",
      "0.418248200"
    ],
    [
      "0.089020024",
      "0.903081725"
    ],
    [
      "0.465505597",
      "0.581751800"
    ],
    [
      "0.322232786",
      "0.429939759"
    ],
    [
      "0.098062427",
      "0.093201679"
    ],
    [
      "0.075685318",
      "0.675865127"
    ],
    [
      "0.415937300",
      "0.257437993"
    ],
    [
      "0.925733945",
      "0.712280483"
    ],
    [
      "0.502000573",
      "0.915736338"
    ],
    [
      "0.702253777",
      "0.912596295"
    ],
    [
      "0.767798624",
      "0.731335404"
    ],
    [
      "0.604659110",
      "0.246814663"
    ],
    [
      "0.924314682",
      "0.324134872"
    ],
    [
      "0.297746222",
      "0.087403705"
    ],
    [
      "0.298790461",
      "0.923514641"
    ],
    [
      "0.897318532",
      "0.526064924"
    ],
    [
      "0.214548192",
      "0.772686081"
    ],
    [
      "0.074266054",
      "0.287719516"
    ],
    [
      "0.910979976",
      "0.096918275"
    ],
    [
      "0.701209538",
      "0.076485358"
    ],
    [
      "0.901937573",
      "0.906798321"
    ],
    [
      "0.584062700",
      "0.742562007"
    ],
    [
      "0.738327726",
      "0.403168325"
    ],
    [
      "0.102681468",
      "0.473935075"
    ],
    [
      "0.785451807",
      "0.227313919"
    ],
    [
      "0.261672274",
      "0.596831674"
    ],
    [
      "0.395340890",
      "0.753185337"
    ]
  ]
}

提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 30
}

当前第一名的答案

{
  "points": [
    [
      "0.677767216",
      "0.570060241"
    ],
    [
      "0.497999427",
      "0.084263662"
    ],
    [
      "0.232201376",
      "0.268664598"
    ],
    [
      "0.534494404",
      "0.418248200"
    ],
    [
      "0.089020024",
      "0.903081725"
    ],
    [
      "0.465505597",
      "0.581751800"
    ],
    [
      "0.322232786",
      "0.429939759"
    ],
    [
      "0.098062427",
      "0.093201679"
    ],
    [
      "0.075685318",
      "0.675865127"
    ],
    [
      "0.415937300",
      "0.257437993"
    ],
    [
      "0.925733945",
      "0.712280483"
    ],
    [
      "0.502000573",
      "0.915736338"
    ],
    [
      "0.702253777",
      "0.912596295"
    ],
    [
      "0.767798624",
      "0.731335404"
    ],
    [
      "0.604659110",
      "0.246814663"
    ],
    [
      "0.924314682",
      "0.324134872"
    ],
    [
      "0.297746222",
      "0.087403705"
    ],
    [
      "0.298790461",
      "0.923514641"
    ],
    [
      "0.897318532",
      "0.526064924"
    ],
    [
      "0.214548192",
      "0.772686081"
    ],
    [
      "0.074266054",
      "0.287719516"
    ],
    [
      "0.910979976",
      "0.096918275"
    ],
    [
      "0.701209538",
      "0.076485358"
    ],
    [
      "0.901937573",
      "0.906798321"
    ],
    [
      "0.584062700",
      "0.742562007"
    ],
    [
      "0.738327726",
      "0.403168325"
    ],
    [
      "0.102681468",
      "0.473935075"
    ],
    [
      "0.785451807",
      "0.227313919"
    ],
    [
      "0.261672274",
      "0.596831674"
    ],
    [
      "0.395340890",
      "0.753185337"
    ]
  ]
}

提交 points。每个坐标写成十进制字符串，例如 "0.25"，最多九位小数。分数是整个单位正方形上的平均平方距离，越小越好。 · 验证器 v1.0.0

DISCUSSION

讨论区

欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖；发言使用与排行榜一致的公开署名，并附带唯一注册编号（#UID）以防冒名。新发言经审核后公开。

暂无讨论，欢迎发表第一篇帖子。