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

Question

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?

If anyone had read that section, please enlighten me. Thank you

Answer 1

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 less¹ 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.}