# In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive?

In CLRS, Section 33.1, we are given the any-two-segments-intersect algorithm. It's a cool algorithm for sure but going through the correctness proof, I don't know how they arrived at the following conclusion:

"Given that we have two segments (call them $$a$$ and $$b$$) that intersect at some point $$p$$, then there must be some sweep line $$x$$ for which the intersecting segments $$a$$ and $$b$$ are consecutive in the total preorder."

Why must $$a$$ and $$b$$ be consecutive at some sweep line?

I do see why visually using the figure 33.4 (page 1023) but I don't know how to prove this statement. How can I prove it?

Note that the statement you want prove is equivalent to showing that the shaded triangles in figure 33.4b are non-empty, or more precisely (for the left triangle) that there exists a vertical line $$x$$ with x-coordinate strictly less1 than $$p$$ such that the triangle enclosed by segments $$a,b$$ and line $$x$$ does not contain a point of any other segment.
To show this, take a vertical line $$x'$$ to the left of $$p$$ that intersects both $$a$$ and $$b$$. The triangle enclosed by segments $$a, b$$ and line $$x'$$ may contain or intersect with a number of other segments. Of those segments, consider the segment with the rightmost point of intersection with the triangle, call this point $$q$$. Note that $$p\neq q$$, since the assumption was made that no three input segments intersect at a single point. Since $$q$$ lies in the triangle, its x-coordinate $$q.x$$ is strictly less than $$p.x$$. Now take a line $$x$$ with an x-coordinate in the open interval $$(q.x,p.x)$$, then no other segments intersect with the triangle enclosed by $$a,b,x$$.
Note that this proof also shows that line $$x$$ can be taken arbitrarily close to the right endpoint of some segment, which are the lines that the algorithm considers.
Although this proof fails when a third segment intersects at $$p$$, you can still show that for any intersection point $$p$$, there exists a pair of segments $$a,b$$ that intersect at that point such that they are consecutive in the partial order, using similar ideas.
1: Depending on the definition of "consecutive", a line with x-coordinate equal to that of $$p$$ would do, but this is not useful for the algorithm.