Question about problem linear programming math modeling

Question

Consider points $A(4.7,−4.1,−1.5)$,$B(−0.4,−2.4,1.9)$,$C(−0.3,−2.1,−6.5)$ and $D(2.7,−3.6,4.0)$. How to discover if segment $AB$ has intersection different of zero with the segment $CD$? Formulate this problem as a linear programming problem.

Answer 1

As I suggested above, it certainly seems to me that linear programming is a poor way to go about this. Nevertheless, this is an LP model that would accomplish this: \begin{array}{ll} \text{minimize} & 0 \\ \text{subject to} & 4.7 t_1 - 0.4 ( 1 - t_1 ) = -0.3 t_2 + 2.7 ( 1 - t_2 ) \\ & -4.1 t_1 - 2.4 ( 1 - t_1 ) = -2.1 t_2 - 3.6 ( 1 - t_2 ) \\ & -1.5 t_1 + 1.9 ( 1 - t_1) = -6.5 t_2 + 4.0 ( 1 - t_2 ) \\ & 0 \leq t_1, t_2 \leq 1 \end{array} This is a feasibility problem: there's no objective to minimize, so I put a dummy objective of $0$, as is common practice. That doesn't make the problem trivial: the linear programming algorithm must still determine valid values of $t_1,t_2$ or conclude that the model is infeasible.

$t_1$ and $t_2$ represent the relative location on each segment:

• On AB, $t_1=1$ corresponds to $A$, $t_1=0$ corresponds to $B$;
• On CD, $t_2=1$ corresponds to $C$, $t_2=0$ corresponds to $D$.

So for instance, if the solution is $t_1=t_2=0.5$, these segments intersect right at their midpoint.

But this is like cracking open a peanut with a sledgehammer. Here's what I would do instead. First, solve the first two equations for $t_1$ and $t_2$.

1. Solve the first two equations for $t_1$ and $t_2$.
2. If $t_1\not\in[0,1]$ or $t_2\not\in[0,1]$, STOP; there is no intersection.
3. Check if the third equation is satisfied for this value of $t_1$ and $t_2$. If it is, then this is your answer; if not, then there is no intersection.

No need for a linear program at all; just a 2x2 linear system and a few checks. For general $A,B,C,D$, you'll need more checks to handle situations like collinearity. But in this case, you get $(t1,t2)=(0.4118,-0.3333)$ just like you would with the LP.