Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

Any comments are apprechiated.

share|improve this question
I'm unclear on the notation. In particular you write some inequalities involving linear combinations of a,b,c,d but these are points as I understand them. So what does an inequality between two points mean? – hardmath Jan 30 at 22:36
I guess user60320 means that that the inequalities hold component wise, looking at a, ..., d as 2d-vectors – stefan Jan 31 at 2:12
Perhaps I should have complained instead about "minimizing" the pair $x,y$. – hardmath Feb 1 at 15:06

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.