整理日期：2026-10-16。 前置笔记：02 基本区域、格行列式与正交化、04 基本计算格问题：SVP、CVP 与 SIVP、05 格基约化与 LLL 算法。
本篇使用欧氏范数，先讨论满秩情形：
记 \(b_1^*,\ldots,b_n^*\) 为 Gram–Schmidt 正交化向量。
目标是找到 \(v\in\Lambda\)，使 \(\|t-v\|\) 尽可能接近
1. 为什么叫“最近平面”#
固定最后一个基向量的整数系数，可以把格分成若干层：
$$ \Lambda#
\bigcup_{c\in\mathbb Z} \left( c b_n+\mathcal L(b_1,\ldots,b_{n-1}) \right). $$
每一层位于一个仿射超平面
这些超平面互相平行，法向量为 \(b_n^*\)，相邻平面的距离为 \(\|b_n^*\|\)。因此，离 \(t\) 最近的平面对应
$$ c_n#
\operatorname{round} \left( \frac{\langle t,b_n^\rangle}{|b_n^|^2} \right). $$
算法先选这一层，再在该层中处理剩余的基向量，逐步把问题降到一维。
这里采用的是贪心选择：最近的平面不一定包含最近的格点，所以一般只能得到近似解。
2. 算法步骤#
NearestPlane(B, t):
计算 B 的正交化向量 b₁*, …, bₙ*
r ← t
v ← 0
对 i = n, n−1, …, 1:
c ← round(〈r, bᵢ*〉 / ||bᵢ*||²)
v ← v + c bᵢ
r ← r − c bᵢ
返回 v其中 round 表示取最近整数；恰好位于中点时，固定采用一种取整规则即可。
理解算法时，需要区分两个操作：
- 计算系数使用 \(b_i^*\)：利用正交方向判断当前目标离哪一层最近。
- 更新残差使用 \(b_i\)：每次减去原格中的向量，保证最终输出仍属于 \(\Lambda\)。
每轮都对当前残差 \(r\) 计算系数。按下标从大到小处理，是因为后续使用的 \(b_1,\ldots,b_{i-1}\) 都与 \(b_i^*\) 正交，不会改变已经处理好的这个方向。
最终
3. 任意基下的误差上界#
每个正交方向都进行了一次最近整数取整，因此最终误差可以写成
由正交性，
这个结论对任意格基成立，但它给出的是由当前基决定的绝对误差上界，还没有说明误差相对最优距离有多大。相关几何解释和残差性质见 Micciancio《Basis Reduction》，Fall 2017，§2，第 3–5 页，尤其 Lemma 5。
4. 配合 LLL 得到近似 CVP 算法#
先使用第五篇的 LLL 算法约化输入基，再运行最近平面算法：
得到
因此，这一组合是一个多项式时间的 \(2^{n/2}\)-近似 CVP 算法。这里固定 LLL 参数 \(\delta=3/4\)，复杂度按整数基和有理目标的输入位长计算。见 Regev《Lecture 3: CVP Algorithm》，Fall 2004，第 1 页算法及第 3–4 页 Lemma 6。
近似保证的证明只需记住两个要点。
首先，LLL 条件给出
于是
其次，比较算法选中的层与一个最近格点所在的层：
- 如果处于同一层，就在这一层中递归分析。
- 如果处于不同层，最优距离至少为半个层间距，即 \(\|b_n^*\|/2\)。结合上面的误差上界，就能控制相对误差。
LLL 控制正交化长度之间的关系，使逐层取整的误差能够与最优距离建立联系。
5. 一个二维例子#
沿用第二篇的基：
其正交化向量为
这组基本身已经满足 \(\delta=3/4\) 的 LLL 条件。
取目标
先处理第二个方向：
$$ c_2#
\operatorname{round} \left( \frac{\langle t,b_2^\rangle}{|b_2^|^2} \right)#
\operatorname{round}\left(\frac9{20}\right) =0. $$
因此选中 \(y=0\) 这一层，残差仍为 \(t\)。
再处理第一个方向：
$$ c_1#
\operatorname{round}\left(\frac35\right) =1. $$
算法输出
但另一层中的格点 \(b_2=(1,2)\) 满足
这说明：即使输入基已经经过 LLL 约化，最近平面算法仍可能错过真正的最近格点。
另外，若直接对原基坐标取整，
$$ B^{-1}t#
\begin{pmatrix} 3/8\ 9/20 \end{pmatrix}, \qquad B,\operatorname{round}(B^{-1}t)=(0,0). $$
它与最近平面算法的输出不同。两者的区别在于：直接坐标取整一次性处理原基坐标；最近平面算法沿正交方向，依据当前残差逐层取整。
LLL 提供基的质量保证，Babai 算法利用这组基逐层选取格点；二者结合，得到具有明确近似因子的 CVP 算法。