6.3 增量算法
(Incremental Algorithm)

现在我们已经准备好来讨论构建直线排列算法。首先，我们必须确定输入和输出。输入很简单，任何直线表示形式，例如斜率和截距，都可以。 输出尚未明确。但我希望，在我们讨论了多面体的面的数据结构(4.4 节)之后， 大家应该能够清楚地认识到，只需稍作修改以适应无界边，任何一种数据结构都可以用来表示排列。特别的，可以直接使用四边数据结构(quad-edge)，因为它能够表示任何细分。 而双生边结构(twin-edge)的半边的设计与排列的组合性质非常契合。我们不会深入探讨表示问题，而只是假设这种表示形式允许轻松遍历包围某个面的边，以及在相邻面之间移动。

构建排列的增量算法(Algorithm6.1)非常简单。在任何给定阶段，我们都有前 \(i-1\) 条直线构建的排列 \(\mathcal{A}_{i-1}\)。 迭代任务是找到 \(\mathcal{A}_{i-1}\) 与第 \(i\) 条输入直线 \(L_i\) 的所有交点。首先，在常数时间内找到 \(L_i\) 与 \(\mathcal{A}_{i-1}\) 中任意一条直线的交点 \(x\)。 在图 6.5 中，\(x = L_i \cap L_2\)。然后我们沿着 \(L_i\) 的区域(zone) \(Z(L_i)\) 顺时针遍历每个面的边，每个面都遍历一遍，直到再次遇到一条穿过 \(L_i\) 的边。 因此在图 6.5 中，我们在遇到 \(L_3\) 和 \(L_i\) 的交点之前遍历了 \(C\) 的三条边。然后我们遍历 \(D\) 的三条边。如此迭代，如图所示。 当遇到无限区域的边时中止。然后从 \(x\) 开始向后重复该过程，逆时针遍历面的边，图中的面 \(B\) 和 \(A\)。此遍历中的每一步都在关联或相邻的对象之间移动，因此每一步都需要常数时间。 插入遍历的总成本取决于区域的复杂度，正如我们在定理 6.2.2 中看到的，其复杂度为 \(O(n)\)。 注意排列的结构是如何被用来避免排序的。只有在找到所有与 \(L_i\) 的交点之后，或者在遍历过程中，\(\mathcal{A}_{i-1}\) 的数据结构才会被更新为 \(\mathcal{A}_i\) 的数据结构。 这也可以在 \(O(n)\) 时间内完成，我们将其留作练习 6.4.1[1]。

显然，整个构建过程需要 \(O(n^2)\) 的时间，这一结果最早由 Chazelle et al.(1985) 和 Edelsbrunner et al.(1986) 得出: