正方形内均匀采样：三角晶格取等分类与交错行族的精确优化

摘要

研究单位正方形内 n 个点的均匀度 M=2h/δ，其中 h 为覆盖半径、δ 为最小点对距离。证明对每个 n≥5，M≥2/√3，且取等点集必为完整三角晶格窗口。对 n≥10，进一步证明晶格必须与正方形对齐，并以两个整数不等式完整分类取等点数。另给出一类交错矩形点阵的精确目标函数及三种族内最优机制。由此确认 P56 的 n=7、8、14、20、22、23、30 的连续全局最优值；但不宣称 n=33、35 或任意 n 的通解。

下载完整论文（Markdown） ↓

1. 问题、范围与文献背景

令 Q=[0,1]²，P⊂Q 含 n 个互不相同的点。定义如下；Mₙ 表示在实数坐标点集上的下确界，先不施加网站的小数限制。

δ(P)=min{‖p−q‖: p,q∈P, p≠q}; h(P)=max{x∈Q} min{p∈P} ‖x−p‖; M(P)=2h(P)/δ(P); Mₙ=inf{|P|=n} M(P).

这就是覆盖与分离之间的 gap ratio；有些文献的 mesh ratio 定义为 h/δ，相差因子 2。所谓蜂窝布局，在这里指点位构成三角晶格、内部 Voronoi 单元为六边形，而不是把点放在蜂窝图的顶点。

Bishnu 等 [1] 研究连续、离散空间中的 gap ratio；其正方形引理给出趋近 2/√3 的有限点数下界。Teramoto 等 [2] 研究在线插点，这是不同于本文离线优化的问题。Bondarenko、Hardin 与 Saff [3] 研究最优装填和 Riesz 能量点集的 mesh ratio。本文集中处理有限正方形的取等刚性、边界兼容性及一个可精确优化的行族；本文为本站自发表研究稿，未经外部同行评审，也不作优先权或“首次发现”声明。

任意 n≥2 的最优值实际达到。取一个非空子水平集 M≤U。由半径 h 的 n 个圆盘覆盖 Q，1≤nπh²，因此 δ≥2/(U√(nπ))。该子水平集在紧集 Qⁿ 中一致远离点重合；h、δ 连续，故 M 在其中达到最小值。后文因此可以把“不取等”加强为“最优值严格大于下界”。

2. Voronoi 边界连通引理

引理。若 h<1/2 且 δ>√2h，则每个裁剪 Voronoi 单元 Vₚ 与 ∂Q 的交连通；所有非容器 Voronoi 边及其端点组成的图 G 连通，而且 G 在容器边界上的顶点度数均为 1。

证明。Vₚ 内任一点到 p 不超过 h，所以其直径不超过 2h<1，不能同时接触相对两墙。若接触相邻两墙，转移至两坐标轴，写 p=(u,v)，0≤u,v≤h，不妨 u≥v。设另一站点 q 到角点的距离 s≤r=√(u²+v²)。q 的坐标非负，故 p·q≥v(qₓ+qᵧ)≥vs。

‖p−q‖²≤r²+s²−2vs≤max{r²,2r(r−v)}≤2u²≤2h²<δ².

中间取 s∈[0,r] 上凸二次函数的端点最大值，最后用 r²≤2u² 和 r(r−v)=u²+v²−rv≤u²。因此 p 是角点唯一最近站点，凸性使两墙上的交区间在角点连接。每个 Vₚ 的非容器边界于是是一条连通弧（保留端点）或一个闭环。

取 G 内两个点，以 Q 内部的一般位置路径相连。逐个把路径穿越单元的片段替换为该单元非容器边界上的路径，得到 G 内的路径，证明连通。墙上若有三个最近站点，它们在同一半圆上，至少一对圆心角≤90°，推出 δ≤√2h；角点甚至不可能有两个最近站点。故边界图顶点只能是度 1 的端点。退化情形使用几何 Voronoi 图，不把共线边的人为细分计作新顶点。∎

3. 有限点数下界与取等刚性

定理 1。对每个 n≥5，Mₙ≥2/√3。若点集取等，则存在边长 δ 的三角晶格 Λ，使 P=Λ∩Q。

证明。只需讨论 M≤2/√3。把 Q 分成四个小正方形，并把边界点任选分配给其中一个，抽屉原理给出 δ≤1/√2。因此 h≤1/√6<1/2，且 δ>√2h，上节引理适用。G 必须有内部顶点：否则每个分量只能是一条边界到边界的直弦；连通性迫使只有一条弦、只有两个单元，与 n≥5 矛盾。

内部顶点的至少三个最近站点共圆，半径 R≤h。至少一个圆心角≤120°，故 δ≤√3R≤√3h，得到下界。取等时恰有三个站点，圆心角全为 120°、R=h，它们组成边长 δ 的等边三角形；四个站点会迫使 δ≤√2h，不可能。

G 连通且边界端点度为 1，所以内部顶点经内部边互相连通；每条边至少有一个内部端点，否则构成独立弦分量。每个站点的单元都有非容器边，故每个站点属于某个内部三角形。相邻内部顶点对应的等边三角形共用一条 δ 边，第三点位于边的两侧，因此同一个三角晶格沿 G 传播至全部站点。最后，若 Λ∩Q 中遗漏一个格点 q，它到 P 的距离至少 δ>h，与覆盖矛盾。因此 P=Λ∩Q。∎

4. 交错矩形点阵的精确公式

取整数 K≥L≥1、K≥2，相位 e∈{0,1}，以及 1≤t≤K/L。以下定义给出上下对称留白的点阵；t 调节纵横比。

a=1/K, b=t/K, m=(1−Lb)/2; P(K,L,e,t)={(ia,m+jb): 0≤i≤K, 0≤j≤L, i+j≡e (mod 2)}.

N(K,L,e)=((K+1)(L+1)+(−1)ᵉ)/2 if K,L are even; otherwise N(K,L,e)=(K+1)(L+1)/2.

定理 2。此点阵的距离、覆盖半径和目标值如下，目标值与相位无关（点数可能相关）。

δ=a min{2,√(1+t²)}; h=a max{(1+t²)/(2t),√(1+(K−Lt)²/4)}; M=2 max{(1+t²)/(2t),√(1+(K−Lt)²/4)}/min{2,√(1+t²)}.

证明。最近邻向量的候选长度为 2a、√(a²+b²)、2b；b≥a，且该有限点阵包含前两个候选点对，得到 δ。无限交错点阵的基本三角形底为 2a、高为 b，覆盖半径 R=(a²+b²)/(2b)。b≥a 时这些三角形构成 Delaunay 三角剖分（b=a 时可共圆退化）：横边对角为 2 arctan(a/b)≤90°，斜边对角为 arctan(b/a)<90°，相邻对角和不超过 180°。外接圆心位于三角形内或边上，空圆半径确为 R。

中央矩形 B=[0,1]×[m,1−m] 的四边反射保持无限点阵。把一个最近站点反复反射折回 B，不增加它到 B 内给定位置的距离，因此 B 上覆盖半径≤R；两种相位各有完整基本三角形位于 B，故 R 达到。上下条带到极端一行的距离至多 C=√(a²+m²)。在底边选择底行缺失的一列，其横向邻居距离恰为 C；第二行及以上距离至少 m+b≥C。所以 C 也达到，h=max{R,C}。∎

5. 三种族内最优机制

推论 2.1。固定 K,L,e，只在上述行族内优化 t，可完全求解。A：若 K/L≤√3，高度不足，t*=K/L，M*=√(1+(L/K)²)。B：若 √3L≤K≤√3L+2/√3，取 t*=√3，M*=2/√3。C：若 K>√3L+2/√3，最优 t* 是 (√3,K/L) 中下面方程的唯一根。

(t+1/t)/2=√(1+(K−Lt)²/4); (L²−1)t⁴−2KLt³+(K²+2)t²−1=0; M*=(t*+1/t*)/2.

证明。t≤√3 时，内部项除以分离距离为 √(1+t²)/(2t)，严格递减；边界项的分子递减、分母递增，亦递减。t≥√3 时分离距离固定为 2a，内部项递增、边界项递减。最优只能在允许端点、t=√3，或两项唯一交点。这三种情形分别给出 A、B、C。∎

例如 (K,L,e)=(9,5,0) 给出 n=30 的全局最优；(10,5,0) 给出 n=33 的族内值 (7√31−25)/12≈1.164529211651；(9,6,0) 给出 n=35 的族内值 √13/3≈1.201850425155。后两者只是具体构造族的最优，不是对任意点位变形的下界。

6. n≥10 的取等晶格必须对齐

引理。n≥10 的取等点集，其三角晶格有一族格线平行于正方形边。证明只需排除非零方向，不依赖数值扫描。由正方形的 90° 对称、晶格的 60° 对称及反射，可约化至 0≤θ≤15°。假设 θ>0，按 δ=1 归一化，覆盖半径 r=1/√3。把有限点集扩充到 x≥0 的整个晶格半平面，只增强对左墙的覆盖。

a⃗=(cos θ,sin θ), b⃗=(cos(60°+θ),sin(60°+θ)), A=cos θ, c=cos(60°+θ), p=√3/2.

沿 a⃗ 的第 j 行与墙交于 Yⱼ，相邻交点相差 p/A。该行第一个非负横坐标格点为 (xⱼ,yⱼ)，其中 0≤xⱼ<A，yⱼ=Yⱼ+xⱼtanθ，且 xⱼ₊₁≡xⱼ+c (mod A)。因为 A>r，同行只有这个点可能服务墙，其区间为 Iⱼ=[yⱼ−√(r²−xⱼ²),yⱼ+√(r²−xⱼ²)]（xⱼ>r 时为空）。

不回绕时，两圆心相差 b⃗、距离为 1，半径 r 的两圆交集最左坐标为 xⱼ+c/2−sin(60°+θ)/(2√3)=xⱼ−sinθ/√3。因此两个墙面区间重叠当且仅当 xⱼ≤sinθ/√3。此处交集最左点确为圆交点：沿水平左移的单圆极点不在另一圆内（cos(60°+θ)<√3/2）；交集最右端横坐标为正。

回绕时令 x′=xⱼ₊₁≥0，同样计算得到交集最左坐标 x′+sinθ/√3>0，所以不重叠。连续两个不回绕重叠也不可能：需要 xⱼ+c≤sinθ/√3，但 c−sinθ/√3=(√3cosθ−5sinθ)/(2√3)>0，因为 tanθ≤2−√3<√3/5（平方后 100<108）。

隔至少两行的圆心纵差至少 √3/cosθ−sinθ≥√3−1/2>2/√3=2r，因此非相邻行不能连接。这些区间局部有限，任一连通覆盖分量至多由两圆组成，其长度不超过 sin(60°+θ)+r+√(r²−c²)。由于 cos75°>1/4，该长度严格小于 1+1/√3+√39/12<101/48；后一个有理界用 48<49 和 16·39<625 验证。单圆分量同样满足此界。

恢复尺度，每个墙面覆盖分量长度小于 101δ/48。n≥10 时把 Q 分成 3×3 小正方形，得 δ≤√2/3，故长度小于 101√2/144<1（20402<20736）。整条单位墙必须位于一个连通覆盖分量，矛盾。因此 θ=0。∎

7. 取等点数的完整整数分类（n≥10）

定理 3。对 n≥10，Mₙ=2/√3 当且仅当存在整数 K≥2、L≥1、e∈{0,1}，满足下列不等式及 n=N(K,L,e)。

3L²≤K², 3K²≤(3L+2)²; equivalently √3L≤K≤√3L+2/√3.

证明必要性。定理 1 和上节使点集为对齐的完整晶格窗口。θ=0 的墙面计算中，相邻行区间重叠要求较近一行恰好贴墙。单圆覆盖长度 2h<1，且非相邻行不能相接，左右墙均需格点贴墙，因而 1=Kδ/2。若水平相邻行距为 √3/K，从最低到最高有 L 个间距，上下边距 tᵦ、tₜ 满足 tᵦ+tₜ=1−L√3/K。

上下墙只由各自极端行覆盖，因为下一行距墙至少 √3δ/2>h。每行至少两点，行内间隔 δ，而最坏横向距离恰为 δ/2。因此 tᵦ、tₜ 分别位于 [0,δ/(2√3)]，正好给出整数不等式。完整性使行内点数按奇偶交替，得到 N 公式。反过来，满足条件时取对称边距 m=(1−L√3/K)/2 和 t=√3，用定理 2 立即达到 2/√3。∎

注意上下边距不必相等：分类允许满足上述条件的全部分配。在 10≤n≤40 内，取等点数仅为 14、20、22、23、30。再由 K=4,L=2 的两相位构造以及定理 1，得到 n=7、8 也全局最优。本定理没有完整分类 n=5、6、9。

取等点数的自然密度为零。每个 L 的 K 区间长度 2/√3<2，至多两个整数，各至多两个点数；又 n≥((L+1)²−1)/2，所以截至 X 只有 O(√X) 个取等点数。特别地 M₃₃、M₃₅>2/√3，但没有得到其精确最优值或显式间隙。这种稀疏性不意味着其他 n 有统一正间隙，也不排除 Mₙ→2/√3。

8. 精确构造、小数证书与竞赛结算

表中每一行都由第 4 节坐标公式配合 t=√3 给出一个精确实数构造，定理 1 为它提供匹配下界。图形仅用于说明；证明不依赖像素或浮点采样。

有限小数坐标不能达到此下界。定理 1 的取等构造必含非退化等边三角形；若三顶点坐标全为有理数，则面积由行列式给出一个有理数，但又等于 √3δ²/4，其中 δ² 是正有理数，矛盾。

P56 验证器从九位小数精确计算 M²，再把 M² 向上取整至 10⁻¹⁵；页面另显示 M 的小数近似。因此不能把 4/3 的内部目标与 2/√3 的显示值混用，也不能放宽容差把近似纪录标为精确最优。

本站据连续问题已解，将 n=7、8、14、20、22、23、30 标记为“已证明最优”并停止竞赛。所有历史纪录、作者归属和既有贡献分保留；当前证书不被宣称为九位网格上的最优。其他子题继续开放，尤其不因为规则构造的数值与纪录吻合而关闭 n=33、35。

9. 结论与可复核性

本文完成的是有限点数的统一下界、取等构型刚性、n≥10 的全部取等点数分类，以及一个双整数、一连续参数构造族的精确优化。它把一些独立数值纪录组织为可证明的结构理论，但不是任意 n 的最优值通解。一般非取等点集的全局优化仍需新的论证，不能假定它们沿用本行族拓扑。

复核只需整数运算即可枚举分类条件；坐标及目标公式均已在文中给出。配套测试检查点数、整数条件、已证明最优的子题名单，以及小数化构造通过现有精确验证器但并未达到 4/3。这些测试验证实现与公式的一致性，不替代上面的解析证明。

署名：MinMax Arena／极值竞技场。研究讨论、推导整理与代码复核使用了 Claude 与 Codex；它们作为辅助工具披露，不代表外部同行审稿人。欢迎就证明漏洞、遗漏先前文献或更强结果在 P56 讨论区提出更正。版本：2026-09-07，v1。

参考文献

[1] Bishnu, Desai, Ghosh, Goswami and Paul — Uniformity of point samples in metric spaces using gap ratio (2015) ↗

[2] Teramoto, Asano, Katoh and Doerr — Inserting Points Uniformly at Every Instance (2006) ↗

[3] Bondarenko, Hardin and Saff — Mesh ratios for best-packing and limits of minimal energy configurations ↗