数学大学
C. Extreme Edges
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
C. Extreme Edges
计算几何 · 01. Convex Hull
Definition
极边：其余所有点都位于该边同一侧的边——极边连成的多边形就是凸包。
定义
有向边 ⟨p,q⟩ 若所有其他点都在左侧，则为极边
与极点关系
极边的端点必是极点
Algorithm
极边算法：枚举所有点对，逐对检查其余点是否同侧，O(n³)。
流程
枚举点对 → 同侧检查 → 收集极边
复杂度
比极点策略的 O(n⁴) 降一阶
Demonstration
演示：小规模点集上逐对验证，直观看到极边逐条被筛出。
演示要点
非极边的两侧都有点，立即淘汰
收尾
按首尾相接关系把极边串成凸包
本节要点
- ✓极边：其余点全在一侧的边
- ✓枚举点对 O(n³) 同侧检查
- ✓极边按连接关系串成凸包
延伸主题：实现极边算法对比极点法的运行时间
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1极边法比极点法快一阶，共同的改进方向是什么？
参考答案两者都停留在「逐候选全局检查」的暴力框架。改进方向是减少候选与检查成本：增量法把问题降为逐点插入，Graham 扫描用排序一次性确定次序——从 O(n³)/O(n⁴) 逼近 O(n log n)。
2极边算法枚举的是「无向点对」，输出时如何恢复方向？
参考答案枚举时不区分 ⟨p,q⟩ 与 ⟨q,p⟩，检查时只要求全部点在同一侧；收集完极边后，再按「每条极边的终点是另一条极边的起点」的规则把它们串成有向闭环，即凸包边界。
3极边法与极点法能否结合出更快的「半暴力」算法？
参考答案可以：先 O(n²) 找出所有极点（用 ToLeft 逐对测试的变体），再只对极点排序连线。这种折中思路正是从 O(n⁴) 迈向高效算法的过渡台阶。