数学大学
F. Lower Bound
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
F. Lower Bound
计算几何 · 01. Convex Hull
Reduction
归约：把问题 A 的求解转化为问题 B 的求解——B 的算法即为 A 的算法。
定义
A ≤ B 表示 A 可在 B 的成本外再加线性成本内解决
方向
由已知算法归约出未知问题的高效解
CAO Chong's Methodology
曹冲称象的方法论：称不动的象转化为称得动的石头——归约思想的古老示范。
转化
把难问题等价转换为易问题
等价性
转换保持答案不变，是归约的合法性核心
Transitivity
归约的传递性：A≤B 且 B≤C，则 A≤C。
传递
归约链可以串联叠加
应用
沿归约链把下界与上界双向搬运
Reduction: Input
从排序归约到凸包（输入侧）：凸包算法的输出可还原出排序结果。
构造
把每个数 aᵢ 变为点 (aᵢ, aᵢ²)
性质
这些点全部落在抛物线上，全为极点
Reduction: Output
输出侧还原：凸包按 x 坐标序遍历顶点，即得到排序后的序列。
还原
沿凸包一侧遍历，x 坐标单调即为有序
结论
排序的 O(n log n) 下界传递给凸包
Sorting ≤_N 2d-CH
结论：排序 ≤N 二维凸包——凸包不可能快于排序的下界。
下界传递
排序需 Ω(n log n)，凸包同样需要
意义
说明 Graham 的 O(n log n) 已是最优量级
本节要点
- ✓归约：难问题转化为易问题求解
- ✓曹冲称象是归约思想的古典示范
- ✓排序 ≤ 凸包 ⇒ 凸包下界 Ω(n log n)
延伸主题：写出归约的完整构造用下界论证算法最优性
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1抛物线上的点为什么全都是极点？
参考答案抛物线是严格凸曲线，其上任何点都不落在其余点构成的三角形内；任意两点的连线（弦）都位于曲线的上方，其余点全在弦的下方一侧——每个点都是凸包顶点。
2「曹冲称象」与算法归约的共同精髓是什么？
参考答案不直接攻难题，而是构造一个保持答案的等价转换，把问题搬到自己擅长的领域解决。归约的形式化证明了这种「移花接木」的合法性，使其从巧思升级为方法。
3归约证明下界的逻辑为什么是「反向」的？
参考答案上界用归约是正向的（用已知算法解新问题）；下界则是反向：假设凸包有更快的算法，把它当作排序的子程序，就会突破排序的既有下界，矛盾。因此排序的下界「压」住了凸包。