# LP to test if two Line Segments intersect

I would like to use a linear program to test if two given linesegments $\overline{ab}$ and $\overline{cd}$ do not intersect.

In a high level description I would have an LP of the form

$$min \text{ } x,y$$ s.t. $$xa+(1-x)b > yc+(1-y)d$$ or $$xa+(1-x)b < yc+(1-y)d$$ $$\forall x,y \in [0,1]$$

My problem is the or, since I want an LP and not an IP. Also since this test is part of a larger LP, I can not just test whether the two segments intersect and then negate the result. My second concern is the forall quantifier. Since the constraints really have to hold for all values of x and y.

Perhaps I should have complained instead about "minimizing" the pair $x,y$. – hardmath Feb 1 '13 at 15:06