Seidel 二维线性规划

为什么只需在新边界上找 ​

旧最优点 $z$ 违反新约束。假如新最优点 $z^{\prime }$ 严格位于新半平面内部，沿 $z^{\prime }$ 朝 $z$ 移动一小段仍满足新约束；旧约束和框也因凸性保持满足。$z$ 的字典序目标优于 $z^{\prime }$，而每个比较分量都是线性的，所以这段移动会严格改进第一个不同的分量，矛盾。

证明可先对每个足够大的有限 $M$ 作出，再用仿射式的最终次序实现。它并不要求新的可行域有正面积：若交集只剩点或线段，区间上下界相等的情况仍被保留。

把符号答案变回真实点 ​

设最终形式点为 $p(M)=u+Mw$。对每条原约束 $a_i\cdot p\le d_i$，记

最终可行性保证 $s_i\le 0$，且 $s_i=0$ 时 $r_i\le 0$。对 $s_i<0$ 的行，只需 $M\ge r_i/(-s_i)$。因此可取

这个 $p_0$ 对全部原约束真实可行。即使目标不随 $M$ 增长，也不能直接返回 $u$：某些约束可能正是靠 $M_{0}w$ 才得到满足。

若 $c\cdot w>0$，$p_0,w$ 就给出严格改进射线。若 $c\cdot w=0$，目标恒为 $c\cdot u$，而任意原系统可行点在充分大的框中都出现，故其目标不超过这个值；$p_0$ 达到该值，证明有限最优。$c\cdot w<0$ 不会出现，因为扩大框不会降低最优目标。判断依据是 $c\cdot w$，不是 $w$ 是否为零。

三次修复到达 $(3,2)$ ​

最大化 $3x+2y$，约束为

按输入 ID 从零编号。附件种子7给出顺序 $[4,0,5,3,1,2]$。初始点为 $(M,M)$，前三次修复如下：

最后三个约束都已满足。最优值为 $13$；把 $x+y\le 5$ 与 $2x+y\le 8$ 各乘一后相加，得到 $3x+2y\le 13$，而 $(3,2)$ 取等号。这份两行对偶证书可脱离随机轨迹单独核验。

$w\ne 0$，目标仍有限 ​

约束 $x\le 0,y\ge 100$，目标最大化 $x$。规范形式答案是 $(0,M)$，故 $u=(0,0),w=(0,1)$。这里 $u$ 违反 $y\ge 100$；按全部约束计算得到 $M_0=100$，输出真实最优点 $(0,100)$，目标为零。

若没有任何约束且目标为零，形式答案为 $(M,M)$，$w$ 同样非零，但任意点的目标都是零。若改成最大化 $x$，同一形式方向的目标斜率变为一，才得到无界。这两个测试能直接抓出“见到非零 $w$ 就报无界”的错误。

空集、平行与低维 ​

零法向量约束 $0x+0y\le d$ 在 $d\ge 0$ 时恒真，在 $d<0$ 时单独证明不可行。$x\le 0$ 与 $x\ge 1$ 是两条平行矛盾约束；$x\le 0$ 与 $x\ge 0$ 却只是把可行域压成直线，不能因为平行就报空。

三条 $x\le 0,y\le 0,x+y\ge 1$ 共同不可行，任意两条都可行，展示了为何一般二维不可行证书可能需要三条。边界扫描发现上下界矛盾时，返回当前边界与两条产生冲突界的约束；若涉及形式框，只保留其中的原输入行。为什么把当前边界等式改回原不等式后仍然矛盾？旧规范点满足那两条旧行，却违反当前半平面；如果保留的原行还有一个新可行点，两点间的线段必在当前边界上相交，并仍满足两条旧行，反而得到被区间检查排除的边界可行点。若涉及形式框，先取足够大的 $M$，让假定的新可行点也在框内；旧规范点本就在框内，同一线段论证仍成立。

修复很贵，为什么总期望仍线性 ​

在一个固定的可行前缀集合里，规范最优点可以由至多两条原约束加固定背景框决定。退化时基可能不唯一，但任何删除后会改变答案的约束必须属于每一份基，所以至多两条。不可行前缀则由 Helly 定理理路Helly 定理Helly theorem欧氏 d 维空间中有限凸集族的全局非空交可由至多 d 加一个集合的局部交保证。得到至多三条原约束的矛盾证书；任何删除后恢复可行的约束也必须在该证书中。

把进入第 $i$ 项之后的前缀集固定，其最后一个 ID 均匀分布于这 $i$ 项。触发昂贵修复时，删去最后一项会改变规范答案或可行状态，所以概率至多 $3/i$。一次修复扫描 $i-1$ 条旧约束及四条框约束，因而

加上打乱、普通违反测试和计算 $M_0$，二维核心期望为 $O(n+1)$ 次算术操作，存储为 $O(n+1)$。遇到不可行立即停止只会减少成本；分析时可以把此后状态视为一直不可行。随机性只改变工作量，返回的三类结果都满足精确规格，这是 Las Vegas 算法理路随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。。

在一般 $d$ 维中，违反一条约束后进入 $d-1$ 维，经典分析出现 $d/i$ 的概率因子及递归求解成本，固定维数期望线性的常数呈阶乘量级。[1, Theorem 1] 本页实际执行器只实现二维，不能把二维的区间扫描直接当作任意维的常数时间子程序。

核心、证书提取与位成本分别计 ​

不可行时的小矛盾 ID 在边界扫描中直接留下；无界射线直接来自 $w$。有限最优值还可另求非负乘子 ${\lambda }_i$，使 $\sum {\lambda }_i(a_i,b_i)=c$ 且 $\sum {\lambda }_i{d}_i=c\cdot p_0$。附件的额外证书器枚举最优点处的单条/成对紧法向量，最坏 $O(n^2)$ 次算术操作；这项可选的通用提取不能藏进线性核心时间里。

所有分支采用 精确有理谓词理路精确几何计算Exact geometric computation · EGC让组合控制流由数学上正确的几何谓词符号驱动，并把近似构造与精确判定分离。。每个候选点由至多两条原边界或形式框边界求交得到，二维公式与每条原行的比较只涉及常数个输入系数。输入每数至多 $L$ 位时，约分后的几何数、形式系数和 $M_0$ 都为 $O(L)$ 位；若含约分的有理运算成本为 $A(L)$，核心期望几何成本为 $O((n+1)A(L))$，还须计 ID、打乱和随机位操作。

完整执行器附有直接枚举形式框顶点的独立小实例解法。其三重枚举和逐前缀审计用于检查，均没有包含在核心线性界中。终结任务要求同时交出有限目标、空集和严格改进射线实例，而不是只测一个漂亮多边形。