# Formal proof for detection of intersections for constrained segments

They told me it was off-topic at stackoverflow. So I am trying my luck here. Yes, it's a homework, but I'm looking for some guidance (or related literature) instead of complete solutions.

Please see the drawing that accompanies the question:

I need to come up with a formal proof for the following statement:

Given an arbitrary count of line segments (S1 -- S3 in the drawing) constrained by two vertical lines (M & N) an answer whether there is at least one intersection of the segments (in the whole picture) can be given by checking each of the two segments that have their left endpoints adjacent on M in descending order (in respect to their position on line M).

For example, in drawing checking could be done in such order:

• S1 and S2 (no intersection)
• S2 and S3 (intersection detected)

While it seems very obvious, there shall be a formal proof for that (most likely, a simple one). Any ideas?

-
I would begin be showing that the y-ordering of their endpoints swap on M and N. –  Nicholas Mancuso May 17 '11 at 22:06

Lemma: If two points on the left line S1 and S2 define segments that intersect and there is a third point S3 between S1 and S2, then either S1 and S3 intersect or S2 and S3 intersect.

Proof of lemma: Note that S1, S2, and their intersection form a triangle that is strictly between the two vertical lines. S3 is on one edge of the triangle and the segment starting at S3 enters the interior of the triangle. Therefore, the segment starting at S3 must leave the triangle, so it must intersect either S1 or S2, since they define the other edges of the triangle.

Proof of theorem: We assume that there are two segments that intersect and we need to prove that this implies that there are two segments that intersect and whose left endpoints are adjacent. Call the left endpoints of the intersecting segments S1 and S2. By the lemma there is a point S3 between S1 and S2 that intersects S1 or S2. If S1 and S3 or S2 and S3 are adjacent, then we are done. If not, then note that there are strictly fewer points between S1 and S3 than there are between S1 and S2, since the interval between S1 and S3 does not contain S2. This means that if we repeatedly apply this process to successively smaller intervals the process will eventually terminate, since the intervals contain fewer points and there are only a finite number of points.

Note that this assumes that none of the left-hand points are coincident. However, in this case there are two points that are adjacent, since they are the same, so the theorem is still proven.

-
Once the segments are numerated try to use induction on $n$ which is the number of the segment, checking whether it is intersecting the next one. Good luck
If you define a function which is the difference in height of the two segments an intersection is represented by the function going through $0$ between $M$ and $N$. For $S1, S2$ it is positive at both ends. For $S2, S3$ it is positive on one end and negative on the other.