凸包顶点个数

· · 算法·理论

先给出结论：

坐标值域为 \mathcal{O}(V) 的整点凸包，其顶点个数为 \mathcal{O}\big(V^{2/3}\big)。

证明：不失一般性，我们将值域设为 [0,V]，并且只考虑凸包中斜率大于 0 且递增的部分（右下凸壳），设凸壳上有 n 个点。

考虑凸壳上相邻的两个点 (x_i,y_i),(x_{i+1},y_{i+1})，其斜率为 p_i/q_i，\gcd(p_i,q_i)=1，有：

p_i+q_i \leq (y_{i+1}-y_i)+(x_{i+1}-x_i)

左右两边分别求和，可以得到：

\sum_{i=1}^{n-1}(p_i+q_i) \leq (x_n+y_n)-(x_1+y_1)\leq 2V

设 p+q 第 k 小的分数的 p+q 值为 h_k：

h_k=\left\lfloor \sqrt{2k-\dfrac{7}{4}}+\dfrac{3}{2}\right\rfloor

由于此处的分数不要求 \gcd(p,q)=1，故 \sum h_i\leq \sum (p_i+q_i)，有放缩：

\sum_{i=1}^{n-1}(p_i+q_i)\geq \sum_{i=1}^{n-1}h_i\geq 2\sum_{i=1}^{h_{n+1}-2}\dbinom{i+1}{2}=2\dbinom{h_{n+1}}{3}=\Omega\big(n^{3/2}\big)

因此 n=\mathcal{O}(V^{2/3})。\Box