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?