正交双梳与粗势能预算¶
1. 结论与范围¶
令查询和宿主为同一棵诱导网格树 Q=F，定义两种面积势能类型预算
B_H = Σ_{d≠0} κ_{Q,(0,d)} |G_{F,(0,d)}|，
B_V = Σ_{d≠0} κ_{Q,(d,0)} |G_{F,(d,0)}|。
下面构造一个参数族 k≥2，满足
n=4k+5， N=4k²+10k+9，
B_H=6k⁴+32k³+64k²+58k+20，
B_V=6k⁴+28k³+48k²+40k+20。
因此两种预算均为 Θ(n⁴)，并且
min(B_H,B_V)/(nN)=B_V/(nN) ∼ 3k/8 → ∞。
这严格否定了对所有查询、宿主以 min(B_H,B_V)=O(nN) 结束证明的路线。它没有否定面积势能上界本身，也没有构成原候选算法的复杂度反例。
数值核验只取预先指定的 k=2,3,4，没有随机搜索或扩大参数。结论来自下面的一般构造与计数，不由三个点拟合多项式。
2. 单树坐标和诱导性¶
使用 (行,列) 坐标，令 b=2k+4。第一把梳子为
A = {(y,0):0≤y≤2k}
∪ {(2i,x):0≤i≤k, 0≤x≤2k}。
它有竖直主干和 k+1 条长度 2k 的向右横齿。
第二把梳子为
B = {(b,x):b≤x≤4k+4}
∪ {(y,b+2i):0≤i≤k, b≤y≤4k+4}。
它有水平主干和 k+1 条长度 2k 的向下竖齿。
用以下折线路径连接两把梳子的端点：
(2k,0) → (b,0) → (b,b)，
每段包含全部整数格点。取这三部分的并为 F，并令 Q=F、查询根为 (0,0)。
两把梳子各自是诱导树：平行齿之间留有一整空行或空列。连接路径只在第一把梳子的底端和第二把梳子的左端接入；其水平段与第一把梳子的底齿相隔四行，其竖直段又在第二把梳子以左至少 b 列。没有额外四邻接。因此并集是一棵诱导树，只有指定连接，不产生环。
每把梳子点数为
(2k+1)+(k+1)·2k=2k²+4k+1。
连接路径长 2k+8，两个端点已经在梳子内，所以新增 2k+7 个点。于是
N=2(2k²+4k+1)+(2k+7)=4k²+10k+9。
行、列范围都为 0,...,4k+4，故最小方框边长为 n=4k+5。宿主恰有 2k 个度三点，没有更高度点。
3. 仅用直齿已经足以得到四次方下界¶
对正水平标签 h=(0,d)，一段水平直路所在行是 y 时，其沿边势能差为 dy，而 det(h,z)=-dy，所以
c_h(z)=2dy。
第一把梳子的 k+1 条横齿位于不同的偶数行。对于每个 1≤d≤k，每条齿都提供至少 2k-d+1≥k+1 个交集点，且这些行给出 k+1 个不同势能值。因此
κ_{Q,(0,d)}≥k+1，
|G_{F,(0,d)}|≥(k+1)(2k-d+1)≥(k+1)²。
第二把梳子在竖直标签下完全对称：竖直直路的势能值为 -2d x，不同齿列给出不同值。
所以两种方向都各有 Θ(k)=Θ(n) 个标签，使势能类型数至少 Θ(n)、重叠点数至少 Θ(n²)。计入正负方向，得到简单的共同下界
B_H,B_V ≥ 2(k+1)² Σ_{d=1}^k(2k-d+1)
= k(3k+1)(k+1)² = Ω(k⁴)。
单凭这一一般下界及 nN=Θ(k³)，就已足以否定取两方向较小预算的 O(nN) 猜想。接下来给出完整精确计数，确认两者也是 O(k⁴)。
4. 水平方向的精确类型和交集¶
只需计算正位移 d：负位移的交集是对应平移，势能值整体取负，因此交集大小和不同值个数相同。
4.1 势能类型¶
当 1≤d≤2k 时：
- 第一把梳子保留
k+1条互不连接的水平交集，每条在行2i，势能值为4di； - 连接横路与第二把梳子的水平主干组成一条完整长横路。它的交集，加上可能存在的交集竖齿，仍是一个分量，势能值为
2d(2k+4)； - 中间只有一个道路点的连接竖段各行，不会产生非零水平交集，不能把这两个区域连起来。
上述 k+2 个值互不相同。因此
κ_H(d)=k+2， 1≤d≤2k。
当 2k<d≤4k+4 时，只剩长连接横路的交集，故 κ_H(d)=1；更大的位移交集为空。
4.2 交集大小¶
对于 1≤d≤2k，按三种点来源计数：
|G_H(d)| = (k+1)(2k-d+1)
+(4k+5-d)
+1_{d为偶数}·2k(k+1-d/2)。
第一项来自第一把梳子的横齿，第二项来自长连接横路，第三项来自第二把梳子在主干以下的竖齿重叠。竖齿列相隔二，奇数位移不能使它们重叠。
对于 2k<d≤4k+4，仅有
|G_H(d)|=4k+5-d。
这些分类按行完全覆盖宿主，且不重计主干。求和得
Σ_{d=1}^{2k}|G_H(d)|=3k³+10k²+10k，
Σ_{d=2k+1}^{4k+4}|G_H(d)|=(2k+4)(2k+5)/2。
因此
B_H=2(k+2)(3k³+10k²+10k)+(2k+4)(2k+5)
=6k⁴+32k³+64k²+58k+20。
5. 竖直方向的精确类型和交集¶
5.1 势能类型¶
当 1≤d≤2k 时：
- 第一把梳子及连接部分的交集始终通过列 0 上的连续竖段连接，构成一个势能值为零的分量；
- 第二把梳子的
k+1根竖齿分别留下一个互不连接的竖直交集，所在列为2k+4+2i，势能值为-2d(2k+4+2i)。
这些值也互不相同。因此 κ_V(d)=k+2。
当 2k<d≤2k+4 时，第二把梳子的交集消失，只剩经列 0 连接的一个分量，故 κ_V(d)=1。再大的竖直位移无交集。
5.2 交集大小¶
对于 1≤d≤2k，精确计数为
|G_V(d)| = (k+1)(2k-d+1)
+(2k+5-d)
+1_{d为偶数}·2k(k+1-d/2)
+1_{d为偶数且d≥4}·2k。
四项依次是：第二把梳子的竖齿、列 0 的长连续竖段、第一把梳子的横齿之间重叠，以及第一把梳子某条横齿与连接横路之间的重叠。最后一项的起点是 d=4，因为第一把梳子最下齿与连接横路相隔四行，不能误从 d=2 开始计。
对于 2k<d≤2k+4，仅剩
|G_V(d)|=(2k+5-d)+1_{d为偶数}·2k。
所有非列 0 的上述交集横段都接入列 0 的连续交集，因此确实只有第 5.1 节所列类型，没有由孤立段引入漏掉的势能值。
求和得到
Σ_{d=1}^{2k}|G_V(d)|=3k³+8k²+8k，
Σ_{d=2k+1}^{2k+4}|G_V(d)|=4k+10。
所以
B_V=2(k+2)(3k³+8k²+8k)+2(4k+10)
=6k⁴+28k³+48k²+40k+20。
两式相减为
B_H-B_V=4k³+16k²+18k>0。
故取方向较小值后，仍保留 6k⁴ 的首项。
7. 对后续证明的限制¶
问题不在于选择了不合适的单一方向：两把正交梳子分别让一个方向出现大量势能类型，并同时提供大交集，旋转取较小值也不能解决。
势能预算将某标签的全部查询势能类型数乘以整个宿主交集大小，允许把并非实际发生的类型与道路资源重复相乘。后续若沿势能方法继续，需要保留真实标记使用的类型、分量或候选信息；单独用最终 Q,F 的这两个粗乘积结束证明不可行。
参数族的渐近结论针对允许规模增长的数学模型；用于运行正式程序的输入仍须满足题面限制。