You have a set of line segments and you want to find all intersections.
First sweep line approach:
Use a priority queue
Q for the events as they come, where each event is just an end point of a line segment.
Use an unordered list
L for the status of the sweep line, that is, all the segments that are currently intersecting the sweep line.
If you reach a beginning of a new segment, add it to the status and test it for intersections against all other segment in the status.
If you reach an end of a segment, remove it from the status.
This algorithm is
O(n^2) if for example all segments are intersecting the x coordinate and assuming that you are sweeping from top to bottom.
Second sweep line approach:
It can be proved that we only have to test for intersections horizontally adjacent segments that are currently in the status of the sweep line. If you understand this proof then you can just use an ordered set for the status and come up with an easy
Here's part of the proof that I don't understand:
I don't think this is a clean proof of the lemma. Events are only either end points or intersections. So in practice the sweep line will never have no event points on it and from the image it seems like the sweep line is moving continuously, which is wrong because the sweep line moves from either an end point to another end point or end point to an intersection or an intersection to another end point.
How would you prove this lemma correctly?