Feb 02: Building a segment arrangement
From Jeff Erickson
…Read more Less…
- Too much snow; we're remote again.
- Intersecting pairs ≥ intersection points
- Bentley-Ottman implicitly perturbs coincident intersections alart, but not necessarily in a geometrically consistent way
- Modified event queue records all segments associated with each event point.
- Implement event queue using a balanced BST (to detect duplicates)
- O(d log n) time to handle each event, where d = degree of arrgh vertex
- Overall running time is O((n+I) log n) by Euler's formula