J. Graham Scan: Analysis
数学大学
J. Graham Scan: Analysis
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
J. Graham Scan: Analysis
计算几何 · 01. Convex Hull
Ω(n) Backtracks
扫描中的弹栈（回溯）总次数下界为 Ω(n)：每个点至多压栈一次、弹出一次。
摊还视角
压栈 n 次封顶，弹栈次数不超过压栈次数
下界
凸包有 n 个顶点时至少 n−1 次成功压栈
Planarity
平面点集假设：输入点是平面上的位置点，彼此无序——排序正是引入秩序的第一步。
无序输入
原始点列没有任何顺序结构
有序化代价
排序是引入秩序的必要投入
Amortization
摊还分析：单个点的弹栈可能多次，但总弹栈均摊后每次操作 O(1)。
均摊成本
总成本除以操作数为 O(1)
方法
聚合法或势能法均可证
Simplification
化简：预处理剔除非极点与重复点，让主算法在更小的输入上运行。
预处理
去重、去内点都是有效化简
权衡
化简本身的成本须低于节省的时间
本节要点
- ✓压栈 n 次封顶，弹栈不超压栈
- ✓摊还后每次操作 O(1)
- ✓预处理化简要算成本账
延伸主题：做一次摊还分析练习测试预处理对性能的影响
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1摊还分析中的「势能法」如何应用到栈扫描？
参考答案把栈中元素个数设为势能：压栈使势能上升 1（付 1），弹栈使势能下降（返还信用）。实际成本减去势能变化后，每步摊还成本非负且为常数——总成本自然线性。
2「回溯」在本算法中具体指什么操作？
参考答案指弹栈：新点到来时撤销此前被证明非顶点的栈顶选择。每个点至多被撤销一次，与压栈次数对偶，因此回溯总量线性——这正是摊还分析的结论。
3平面性假设如果去掉（空间点集），凸包算法还能沿用吗？
参考答案不能直接沿用：三维凸包是多面体，极角排序与栈扫描全部失效，需要增量法或分治在三维上重构面片。二维技巧的核心都依赖平面上的转向判定。