Understanding a proof in the sweep line algorithm when finding all line segment intersections

Question

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 O(nlogn) algorithm.

Here's part of the proof that I don't understand:

enter image description here

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?

Answer 1

The proof is absolutely correct. Of course, the algorithm only computes something when the sweep line comes to an eventpoint. Nevertheless you can think of the sweep line as a continiously moving line even if the algorithm does not hold everywhere to compute something.

Therefore you can always find a position, where the sweep line $l$ is close enough to $p$ and has no event point on it. In other words, you can always find a position above $p$ without eventpoints, where $p$ is the next eventpoint (maybe one of many). On this position, $s_i$ and $s_j$ are adjacent. There is no word here, that the algorithm computes something at this point and there is no conflict between the continuously moving sweep line and the discrete computing-positions of the algorithm.

• Ziqi Fan: Intuitively, I agree. But how to give a detailed proof on that?