营业日志 2020.11.19 WF2015 Asteroids 的单峰性证明

> **问题** 有两凸多边形 $A,B$ 进行匀速直线运动。即 $f(t)$ 为在 $t$ 时刻二者交的面积 $\mu (A\cap B)$。求证 $f(t)$ 为单峰函数，且 $f(t) \in (0, f_{\max})$ 的部分恰为两个区间，左侧单调递增，右侧单调递减。 首先让我们进行问题的第一步规约：我们将时间看做第三个维度，那么 $A,B$ 便是一个三维的无穷延伸的斜柱体。接下来我们证明它们都是凸的。 > **引理** $\forall x,y \in A,\forall \alpha \in (0,1), \alpha x + (1-\alpha) y \in A$。 > **证明** 考虑将 $y$ 移动到 $x$ 同时刻的位置 $y^*$，考虑线段 $\overline{x y^*}$ 挪动至 $\alpha x + (1-\alpha) y$ 的所在时刻的线段 $\overline L$，由定义可知 $\overline L \subset A$，而 $\alpha x + (1-\alpha) y \in \overline L$，故 $\forall \alpha \in (0,1), \alpha x + (1-\alpha) y \in A$。$\square$ 类似地，$B$ 也是凸的，故 $A\cap B$ 也是凸的。接下来我们需要引用一个不等式： > **Brunn–Minkowski 不等式** 在 $n$ 维空间上，记 Minkowski 和为 $A+B=\{a+b \vert a\in A,b\in B\}$，那么有 > $$\mu(A+B)^{1/n} \ge \mu(A)^{1/n} + \mu(B)^{1/n}$$ 考虑在凸多面体 $V=A\cap B$ 上，垂直于 $t$ 轴做截面 $X,Y$，考虑 $X,Y$ 之间的任一截面 $Z$，其中时间为 $\alpha t_X + (1-\alpha) t_Y$，那么有 $Z(\alpha) \supset \alpha X + (1-\alpha) Y$。注意到 $\mu(\alpha X)=\mu(X)\alpha^n$，由不等式可得 $$ \mu(Z)^{1/2} \ge \alpha \mu(X)^{1/2} + (1-\alpha) \mu(Y)^{1/2} $$ 由此我们可知，在截面非空的部分，$f(t)^{1/2}$ **是凸函数**。故其为单峰函数。