Sweep Line
Move a line across the plane, processing events in order and maintaining an active set.
Plane Geometry: Sweep finds a crossing at the second event
x = 0: AB begins. It enters the active order by its height here, giving AB. It has no neighbour yet, so there is nothing to test.
Cost
- Best
- O(n log n)
- Average
- O((n + k) log n)
- Worst
- O((n + k) log n)
- Space
- O(n)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Plane Geometry covers these too, in the same run.