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²).
Robustness
Floating-point edge cases (near-vertical lines, near-coincident intersections) plague implementations. LEDA + CGAL use exact arithmetic.