2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.