# How to find the shortest path between two points under the restriction?

Let two different points $M_1(x_1,y_1,z_1)$, $M_2(x_2,y_2,z_2)$ and two nonintersecting lines $l_1$, $l_2$ be given. How to find the shortest path between $M_1$ and $M_2$ which intersects both $l_1$ and $l_2$?

An unimaginative approach is to treat this as minimization of a convex function of two real variables. The input consists of:

• given points $M_1,M_2$
• first line determined by a point $P_1$ and direction vector $v_1$
• second line determined by a point $P_2$ and direction vector $v_2$

The function to be minimized is $$f(s,t)=|M_1-P_1-tv_1|+|P_1+tv_1-P_2-sv_2|+|P_2+sv_2-M_2| \tag1$$ where $|\cdot|$ means Euclidean norm. That is, assuming that we know in which order the lines should be visited. If we don't, then we look for shortest path for each order, and pick the shorter of two.

We can exclude the case where $M_1$ lies on the first line or $M_2$ lies on the second line (because then you would drop that line from consideration and simplify the problem). Then none of the terms in (1) can be zero, which implies that $f$ is differentiable. Its partial derivatives are $$\frac{\partial f}{\partial s} = \left\langle \frac{P_2+sv_2-M_2}{|P_2+sv_2-M_2|}-\frac{P_1+tv_1-P_2-sv_2}{|P_1+tv_1-P_2-sv_2|} ,v_2\right\rangle \tag2$$ $$\frac{\partial f}{\partial t} = \left\langle \frac{P_1+tv_1-P_2-sv_2}{|P_1+tv_1-P_2-sv_2|} - \frac{M_1-P_1-tv_1}{|M_1-P_1-tv_1|},v_1\right\rangle \tag3$$ After staring at (2)-(3) for a little while, I did not find any clever way to solve the system for $s,t$ symbolically.

And we'd have to do numeric comparison of two ways to visit the lines, anyway...

This looks like an appropriate problem for numeric routines, which are happy to minimize differentiable convex functions with few parameters. I tried it in Scilab, although Sage seemed to work about the same.

With your example data, the shortest path is $( - 2, 3, - 4)$, $( 3.8102572, - 0.3794857, - 1.3794857)$, $(2.1548545, - 2.309709, 2.8451455)$, $(4, - 1, 3 )$. Its total length is $14.413266$. Here is the picture (path in red, given lines in blue):

And here is my Scilab code (pretty ugly even by my low standards, mostly because of considering two types of paths).

function [path,path_length,tmin]=findPath(M1,M2,P1,V1,P2,V2)
function d=totalDistance(t)
d=norm(M1-P1-t(1)*V1)+norm(P1+t(1)*V1-P2-t(2)*V2)+norm(P2+t(2)*V2-M2)
endfunction
tmin = fminsearch ( totalDistance , [0,0] )
path_length = totalDistance(tmin)
path = [M1;P1+tmin(1)*V1;P2+tmin(2)*V2;M2]
endfunction

M1 = [-2,3,-4]; M2 = [4,-1,3]
P1 = [3,-4,2]; V1 = [-1,2,1]
P2 = [4,0,-1]; V2 = [1,2,2]

[path1,path_length1,tmin1] = findPath(M1,M2,P1,V1,P2,V2)
[path2,path_length2,tmin2] = findPath(M2,M1,P1,V1,P2,V2)
if path_length1<path_length2 then
path = path1; path_length = path_length1; tmin=tmin1
else
path = path2; path_length = path_length2; tmin=tmin2
end

print(%io(2),path_length, path)
clf()
line1 = [P1+(tmin(1)-2)*V1; P1+(tmin(1)+2)*V1]
line2 = [P2+(tmin(2)-2)*V2; P2+(tmin(2)+2)*V2]
param3d1(line1(:,1),line1(:,2),list(line1(:,3),[2]))
param3d1(line2(:,1),line2(:,2),list(line2(:,3),[2]))
param3d1(path(:,1),path(:,2),list(path(:,3),[5]))

• Vote up is mine. Two paths should be taken into consideration. See my comment to the answer by Angela Richardson. One of the disadvantages of numerical solutions is that the machinery of the phenomenon remains unclear. I have in mind whether the shortest path is formed by reflection. – user64494 Jun 6 '13 at 15:34
• @user64494 Geometrically, equating (2) and (3) to $0$ says precisely that the change of (unit) velocity vector upon touching a line is a vector orthogonal to the line. This behavior is that of a particle bouncing off a line. So in that sense, yes, we have a kind of reflection -- but it does not seem to determine the path as easily as reflection off a codimension 1 plane. – ˈjuː.zɚ79365 Jun 6 '13 at 15:40

There is a shorterst path that touches both lines, but needn't be a shortest path that intersects them. Treat any line that is not between $M_1$ and $M_2$ as a $1D$ mirror and the path as that taken by light with angle of incidence=angle of reflection.

In the worst (two mirror) case, if $l_i$ has direction vector $v_i$ and the ray from $M_1$ initially has direction vector $u$, then if the ray for example touches $l_1$ first then after reflection the new direction vector will be $u'=u-(2u.v_1)v_1$ and after the second reflection $u''=u'-(2u'.v_2)v_2$. From then on the algebra gets tedious.

• @ Angela Richardson : Could you clarify your idea concerning a mirror for a concrete case, say $M_1(-2,3,-4), M_2(4,-1,3)$, and $$l_1: x=-t+3,y= 2t-4,z= t+2, l_2: x=s+4, y= 2s,z= 2s-1?$$ BTW, $l_1$ may be parallel to $l_2.$ – user64494 Jun 6 '13 at 10:57
• See the solution of the above case with Maple here as a PDF file. The two paths are considered: $M_1 \rightarrow A \rightarrow B \rightarrow M_2$ and $M_1 \rightarrow C \rightarrow E \rightarrow M_2$, where $A \in l_1, B\ \in l_2, C \in l_2, E \in l_1.$ – user64494 Jun 6 '13 at 15:20
• @user64494 Hurray, our results agree! – ˈjuː.zɚ79365 Jun 6 '13 at 15:26
• @ user79365 : Yes. You can see that as a PDF file. – user64494 Jun 6 '13 at 15:38
• @ Angela Richardson : I realised your approach with Maple. The symbolic solution is expressed in terms of the roots of a polynomial of degree 8. – user64494 Jun 7 '13 at 4:59