Approach
Sort half-planes by angle. Use deque: pop from back if current makes intersection at back irrelevant. Pop from front similarly.
Advertisement
Complexity
O(N log N) dominated by sort. Deque operations amortized O(N).
Advertisement
Duality
Half-planes ↔ points. Half-plane intersection ↔ convex hull under duality. Both same complexity.
Applications
Linear programming in 2D. Kernel of polygon. Feasible region visualization.