3
$\begingroup$

Possible Duplicate:
Formal proof for detection of intersections for constrained segments

Hi

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?

crossing segments

  • 0
    Ok, if this is off-topic, then I wonder what computational geometry really is. Thanks for suggestions though.2011-05-17

0 Answers 0