FFMP Ex13 解答

约 861 字大约 3 分钟

2026-4-20

自交点数

我们知道平面图的欧拉公式 $V-E+F = 2$ ，由 $E = 2V$ 可知 $F = V + 2$ 。因此，问题转化为最大化路径的自交点数。

如图，一个自交点总是对应唯一的一对（交错）同向角，而每对交错同向角最多对应一个自交点。从而转化为 [Ex 12] 的逆序对问题，可以用组合方法解决。

那有没有更优雅的方法呢？~~穿西装解题之类的方法不在考虑范围内。~~

想象一根线从上到下扫描，记录线与路径交点的个数。

此时，线与路径交点成对出现、成对消失，而自交点数与成对出现/消失时，这对点所成的横线段会与它们之间的每一个点都形成一个自交点。

于是贪心地，我们令所有点的消失都在所有点出现之后。以逆时针为正方向，即向左的边都在向右的边之上。

将第 $i$ 高的向右边与第 $n+1-i$ 高的向右边交换高度。将第 $i$ 高的向左边与第 $n+1-i$ 高的向左边交换高度。

如图：

反转变换

根据扫描线得出的结论，只需讨论所有向左边都在向右边之上的情形，一条合法路径的反转变换结果仍是一条合法路径。接下来，我们来考虑变换前后的自交点数。

如图，反转变换会将交错同向角与不交错同向角互相变换，从而变换前后的交点数不大于 $4\mathrm{C}_{n}^{2}$ 。

引理

若 $n$ 边形的外角和为 $A$ ，自交点数为 $n$ ，则 $n \ge \dfrac{|A|}{2\pi} - 1$ 。

外角

这里的“外角”指将顶点顺次编号后，将 $\overrightarrow{P_{i-1}P_i}$ 以逆时针为正方向旋转至 $\overrightarrow{P_iP_{i+1}}$ 的有向旋转角主值（取 $(-\pi, \pi]$ ）。

红色：逆时针，正外角；蓝色：顺时针，负外角。
图中的多边形不符合原始题意，仅为“外角”定义的演示。

证明

考虑对 $n$ 归纳， $n=0$ 时，根据简单多边形外角和定理，一定有 $|A| = 2\pi$ ，奠基成立。

假设命题对 $0,1,\dots,n-1$ 都成立，下证命题对 $n$ 成立：

由简单多边形外角和定理可知简单多边形的 $|A| = 2\pi$ ，于是 $|A| > 2\pi$ 时多边形一定不是简单多边形，即至少有一个自交点，记作 $P$ 。

将整个多边形从 $P$ 分开，分成两个小多边形。记两个小多边形的外角和、自交点数分别为 $A_1, A_2; n_1, n_2$ ，显然

于是 $n = n_1 + n_2 + 1 \ge (|A_1| - 1) + (|A_2| - 1) + 1 \ge |A_1+A_2| - 1 = |A| - 1$ ，证毕。

设最多有 $V$ 个自交点，最多的图形的经反转变换后有 $v$ 个自交点，于是 $v + V \le 2n(n-1)$ 。

根据 $v \ge n-1$ ，可知 $V \le 4\mathrm{C}_{n}^{2}-(n-1) = 2n^2-3n+1$ 。

注意到以下构造

于是 $V_{\max} = 2n^2-3n+1$ ，即 $F_{\max} = 2n^2-3n+3$ ，~~233！~~

版权归属：Phantom-Bird