单位正方形内的最优量化
文献中也称optimal quantizationquantizer problemcentroidal Voronoi tessellation
在边长为 1 的正方形内放置 n 个点。正方形内的每个位置都归属离它最近的点，计算各位置到最近点的平方距离在整个正方形上的平均值，并把这个平均值压到最低。
严格定义
- 容器单位正方形 [0, 1]²，左下角为原点 (0, 0)，右上角为 (1, 1)
- 提交恰好 n 个点的坐标，写成最多九位小数的十进制字符串；两两不重合
- 归属正方形内每个位置归属离它最近的点（即 Voronoi 剖分）；等距分界线面积为零，不影响积分值
- 分数E(P) 是单位正方形上到最近提交点的平方距离积分（因正方形面积为 1，积分即平均值）；验证器精确计算有理数积分后按 10⁻¹⁸ 向上取整
- 目标在所有合法点集 P 中最小化 E(P)
帮助理解
一个比喻：复活点
把正方形看作一张地图，这 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)，对应正六边形蜂窝剖分的量化误差，而在正方形内无法拼出完整正六边形，因此该下界严格不可达。
所有 n 的当前最佳解
每个规模参数 n 都是一个独立计分的子题。点击任意卡片可查看当前纪录构型，或打开编辑器提交更优解答。
讨论区（0）↓引用与数据
该题族所有子题的权威分数、证明状态、坐标数据与文献来源均汇总于下方稳定链接，按 CC BY 4.0 协议发布。由于分数随纪录刷新而更新，引用时请同时注明文件中的 generatedAt 时间戳。
GET https://minmaxarena.com/data/optimal-quantization.json
引用建议使用 2026-10 冻结归档版：实时纪录会变，但冻结版永久固定，便于日后核查。
GET https://minmaxarena.com/data/editions/2026-10/optimal-quantization.json
BibTeX（点击复制）
@misc{minmaxarena-optimal-quantization-2026-10,
title = {{Optimal quantization in the unit square} (P55)},
author = {{MinMax Arena}},
year = {2026},
note = {Machine-verified records, 2026-10 edition},
url = {https://minmaxarena.com/data/editions/2026-10/optimal-quantization.json},
license = {CC BY 4.0}
}讨论区
欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖；发言使用与排行榜一致的公开署名，并附带唯一注册编号（#UID）以防冒名。新发言经审核后公开。
暂无讨论，欢迎发表第一篇帖子。
按选手与子题归档，默认展示最新一篇。历史版本与回复完整保留，点击即可展开查看或回复。求解笔记可在提交破纪录答案时一并发布。
暂无求解笔记。