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

Elegia · 2020-11-19 18:35:02 · 个人记录

问题 有两凸多边形 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，由不等式可得

由此我们可知，在截面非空的部分，f(t)^{1/2} 是凸函数。故其为单峰函数。