Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 '13 at 22:36
I guess user60320 means that that the inequalities hold component wise, looking at a, ..., d as 2d-vectors – stefan Jan 31 '13 at 2:12
Perhaps I should have complained instead about "minimizing" the pair $x,y$. – hardmath Feb 1 '13 at 15:06

Your Answer


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

Browse other questions tagged or ask your own question.