algorithm - 计算 "Introduction to Algorithms: A Creative Approach"平面中的区域

Question

我正在阅读《算法导论:一种创造性方法》一书。 但是遇到了关于平面上计数区域公式证明的问题。

作者在第13页和第14页用归纳法做了证明。

第 13 页

Thus, we need only to prove that the presence of nth line causes the (n+1)th line to add one additional region

第 14 页

But, the addition of (n+1)th line, when the nth line is present, affects R into two regions(R is cut from two to four regions) instead of just adding one.

看来假设不成立了。但是

Hence, the (n+1)th line adds n regions without the presence of nth line, but it adds n+1 regions with nth line, and the proof is complete.

我真的很困惑。 如何才能证明完整？ 有谁知道为什么？ 提前谢谢你。

Answer 1

让我们首先回顾一下假设:

Adding one more line to N-1 lines in general position in the plane increases the number of regions by N.

N 的假设仅在 (N)th-Line 不存在时使用，以确保 (N+1)th-Line 确实增加了 N 个区域(of当然，当 (N)th-Line 不存在时。)

现在我们要更进一步到N+1的情况。

这里我们有 (N)th 行返回并检查区域 R 和其他区域。在 R 之外，第 (N)th-Line 如何分割区域与 (N+1)th-Line 无关。 (N+1)th-Line 增加 (N-1) 行，不包括 R，无论如何 (N)th-Line作品。此外，由于第 (N)th 行的存在，与原来的 2 个区域相比，R 被分成 4 个区域而不是 3 个区域。因此，第 (N+1) 行贡献了 (N-1) + 2 = N+1 行。

请注意，当我们谈论 R 之外的区域时，(N-1) 行增加了 (N+1)th - 假设 promise 了行N 的假设。此外，当我们谈论 N 的假设时，只有行数很重要，而不是哪一行。因此，假设没有失败，因为我们在没有第 (N)th 行的情况下使用它。

抱歉个人解释冗长，希望对您有所帮助。