Events
Left endpoint: insert into active BST. Right endpoint: remove. Intersection: swap two segments in BST.
Advertisement
BST invariant
Active segments ordered by y-value at current sweep x. Swap on intersection maintains order.
Advertisement
Complexity
O((N+K) log N) where K = # intersections. Worst K = O(N²).