J. Halfplane Intersection Construction
数学大学
J. Halfplane Intersectio
计算几何 · 02. Geometric Intersection
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
J. Halfplane Intersectio
计算几何 · 02. Geometric Intersection
The Problem
半平面交问题：n 个半平面的公共部分是一个凸区域（可能为空）。
半平面
一条直线及其某一侧的全部点
交的形式
凸多边形、无界凸区域或空集
Lower Bound
半平面交的下界：排序可归约到它，故 Ω(n log n)。
归约构造
用半平面编码比较关系
结论
基于比较的算法不可能优于排序下界
Divide-And-Conquer
分治求半平面交：两两求交再合并，凸区域与凸区域的交仍是凸的。
合并
两个凸多边形的交用同步扫描线性完成
递推
T(n)=2T(n/2)+O(n)，总 O(n log n)
本节要点
- ✓半平面交结果是凸区域
- ✓下界 Ω(n log n) 由排序归约
- ✓分治合并线性，总量 O(n log n)
延伸主题：实现两个凸多边形求交构造无解的半平面组
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么半平面交的结果一定是凸的？
参考答案每个半平面都是凸集（取直线一侧后线性约束保持凸性），凸集的交集仍是凸集。无论多少个半平面、什么顺序相交，结果永远是凸区域。
2半平面交与「线性规划可行域」是什么关系？
参考答案线性规划的可行域正是若干线性不等式（半平面/半空间）的交。二维线性规划的可行域求解就是半平面交问题，最优解出现在可行域的顶点上。
3半平面交结果为空集时如何识别？
参考答案合并过程中凸区域面积收缩为零，或两条反向平行的半平面把区域夹灭。实现中在扫描合并时检测可行区域宽度变为非正，即可判空并提前返回。