Return to Question

Given points $P_1,P_2$ on the plane, how do I find the shortest curve from $P_1$ to $P_2$ that passes through a third point $Q$ (which could be anywhere on the plane) ?

I guess the answer should be the line segments $( P_1Q, P_2Q )$, but how do I properly formulate this as a variational problem? Can the same formulation be extended to multiple intermediate points $Q_1,Q_2,...,Q_n $ in some order?

Note: I couldn't get a good answer to a more non-trivial problem I had in mind at Math.SE at http://bit.ly/ezlMoi, hence this post here. I suppose my original problem is not easily solvable, so I am trying to distil it down to its essence.

Edit : I have a purported answer for the case with a 3rd point $Q$. Suppose that $P_1=(p_{1x}, p_{1y})$ and that $P_2$ and $Q$ have a similar representation. Let's write the curve as $y=y(x)$ ; then the length functional is $L(y) = \int_{p_{1x}}^{p_{2x}} \sqrt{1+y'^2} dx$. Also, since the curve passes through $Q$, it needs to satisfy the condition $C: \min | (x-q_x) (y-q_y)|=0$ as the curve takes on values $(x,y)$. Then the problem reduces to "Minimise $L(y)$ subject to $C$" or to minimising $L(y) + \lambda \min | (x-q_x) (y-q_y)|$. Is this correct?

Edit #2 - A new approach I unaccepted Spencer's answer below to present my alternative approach. Please note that my knowledge of calculus of variations is fairly minimal, and I have taken plenty of liberties with rigour.

I'll be more concrete and assume that $P1=(0,0), Q=(.5,.5), P2=(1,0)$; assume the curve is of the form $y=y(x)$ and passes through $P1,P2$ and $Q$ . (Strictly speaking, it should have been $(x(t),y(t))$ to accommodate loops, etc.). Without the pass-through constraint, we would have just set up the Euler Lagrange equations and obtained the following Differential Equation:

$$ \frac{d}{dx} \frac{y'}{\sqrt{1+y'^2}} = 0 (*)$$ subject to $y(0)=0, y(1)=1$.

The pass-through constraint $y(.5) = .5$ cannot be accommodated within the second-order equation above, which admits only two free parameters, supplied by $y(0)$ and $y(1)$. Suppose however that we further differentiate (*), to get :

$$ \frac{d^2}{dx^2} \frac{y'}{\sqrt{1+y'^2}} = 0 (**)$$ subject to $y(0)=0, y(1/2)=1/2, y(1)=1$.

This equation has similar solutions to (*) and admits the pass through constraint as well.

Is the approach shown above valid and extend to multiple intermediate waypoints $Q_1,Q_2..$ ?

Given points $P_1,P_2$ on the plane, how do I find the shortest curve from $P_1$ to $P_2$ that passes through a third point $Q$ (which could be anywhere on the plane) ?

I guess the answer should be the line segments $( P_1Q, P_2Q )$, but how do I properly formulate this as a variational problem? Can the same formulation be extended to multiple intermediate points $Q_1,Q_2,...,Q_n $ in some order?

Note: I couldn't get a good answer to a more non-trivial problem I had in mind at Math.SE, hence this post here. I suppose my original problem is not easily solvable, so I am trying to distil it down to its essence.

Edit : I have a purported answer for the case with a 3rd point $Q$. Suppose that $P_1=(p_{1x}, p_{1y})$ and that $P_2$ and $Q$ have a similar representation. Let's write the curve as $y=y(x)$ ; then the length functional is $L(y) = \int_{p_{1x}}^{p_{2x}} \sqrt{1+y'^2} dx$. Also, since the curve passes through $Q$, it needs to satisfy the condition $C: \min | (x-q_x) (y-q_y)|=0$ as the curve takes on values $(x,y)$. Then the problem reduces to "Minimise $L(y)$ subject to $C$" or to minimising $L(y) + \lambda \min | (x-q_x) (y-q_y)|$. Is this correct?

Edit #2 - A new approach I unaccepted Spencer's answer below to present my alternative approach. Please note that my knowledge of calculus of variations is fairly minimal, and I have taken plenty of liberties with rigour.

I'll be more concrete and assume that $P1=(0,0), Q=(.5,.5), P2=(1,0)$; assume the curve is of the form $y=y(x)$ and passes through $P1,P2$ and $Q$ . (Strictly speaking, it should have been $(x(t),y(t))$ to accommodate loops, etc.). Without the pass-through constraint, we would have just set up the Euler Lagrange equations and obtained the following Differential Equation:

$$ \frac{d}{dx} \frac{y'}{\sqrt{1+y'^2}} = 0 (*)$$ subject to $y(0)=0, y(1)=1$.

The pass-through constraint $y(.5) = .5$ cannot be accommodated within the second-order equation above, which admits only two free parameters, supplied by $y(0)$ and $y(1)$. Suppose however that we further differentiate (*), to get :

$$ \frac{d^2}{dx^2} \frac{y'}{\sqrt{1+y'^2}} = 0 (**)$$ subject to $y(0)=0, y(1/2)=1/2, y(1)=1$.

This equation has similar solutions to (*) and admits the pass through constraint as well.

Is the approach shown above valid and extend to multiple intermediate waypoints $Q_1,Q_2..$ ?

Given points $P_1,P_2$ on the plane, how do I find the shortest curve from $P_1$ to $P_2$ that passes through a third point $Q$ (which could be anywhere on the plane) ?

I guess the answer should be the line segments $( P_1Q, P_2Q )$, but how do I properly formulate this as a variational problem? Can the same formulation be extended to multiple intermediate points $Q_1,Q_2,...,Q_n $ in some order?

Note: I couldn't get a good answer to a more non-trivial problem I had in mind at Math.SE at http://bit.ly/ezlMoi, hence this post here. I suppose my original problem is not easily solvable, so I am trying to distil it down to its essence.

Edit : I have a purported answer for the case with a 3rd point $Q$. Suppose that $P_1=(p_{1x}, p_{1y})$ and that $P_2$ and $Q$ have a similar representation. Let's write the curve as $y=y(x)$ ; then the length functional is $L(y) = \int_{p_{1x}}^{p_{2x}} \sqrt{1+y'^2} dx$. Also, since the curve passes through $Q$, it needs to satisfy the condition $C: \min | (x-q_x) (y-q_y)|=0$ as the curve takes on values $(x,y)$. Then the problem reduces to "Minimise $L(y)$ subject to $C$" or to minimising $L(y) + \lambda \min | (x-q_x) (y-q_y)|$. Is this correct?

Edit #2 - A new approach I unaccepted Doug's answer below to present my alternative approach. Please note that my knowledge of calculus of variations is fairly minimal, and I have taken plenty of liberties with rigour.

I'll be more concrete and assume that $P1=(0,0), Q=(.5,.5), P2=(1,0)$; assume the curve is of the form $y=y(x)$ and passes through $P1,P2$ and $Q$ . (Strictly speaking, it should have been $(x(t),y(t))$ to accommodate loops, etc.). Without the pass-through constraint, we would have just set up the Euler Lagrange equations and obtained the following Differential Equation:

$$ \frac{d}{dx} \frac{y'}{\sqrt{1+y'^2}} = 0 (*)$$ subject to $y(0)=0, y(1)=1$.

The pass-through constraint $y(.5) = .5$ cannot be accommodated within the second-order equation above, which admits only two free parameters, supplied by $y(0)$ and $y(1)$. Suppose however that we further differentiate (*), to get :

$$ \frac{d^2}{dx^2} \frac{y'}{\sqrt{1+y'^2}} = 0 (**)$$ subject to $y(0)=0, y(1/2)=1/2, y(1)=1$.

This equation has similar solutions to (*) and admits the pass through constraint as well.

Is the approach shown above valid and extend to multiple intermediate waypoints $Q_1,Q_2..$ ?

Given points $P_1,P_2$ on the plane, how do I find the shortest curve from $P_1$ to $P_2$ that passes through a third point $Q$ (which could be anywhere on the plane) ?

I guess the answer should be the line segments $( P_1Q, P_2Q )$, but how do I properly formulate this as a variational problem? Can the same formulation be extended to multiple intermediate points $Q_1,Q_2,...,Q_n $ in some order?

Note: I couldn't get a good answer to a more non-trivial problem I had in mind at Math.SE at http://bit.ly/ezlMoi, hence this post here. I suppose my original problem is not easily solvable, so I am trying to distil it down to its essence.

Edit : I have a purported answer for the case with a 3rd point $Q$. Suppose that $P_1=(p_{1x}, p_{1y})$ and that $P_2$ and $Q$ have a similar representation. Let's write the curve as $y=y(x)$ ; then the length functional is $L(y) = \int_{p_{1x}}^{p_{2x}} \sqrt{1+y'^2} dx$. Also, since the curve passes through $Q$, it needs to satisfy the condition $C: \min | (x-q_x) (y-q_y)|=0$ as the curve takes on values $(x,y)$. Then the problem reduces to "Minimise $L(y)$ subject to $C$" or to minimising $L(y) + \lambda \min | (x-q_x) (y-q_y)|$. Is this correct?

Edit #2 - A new approach I unaccepted Spencer's answer below to present my alternative approach. Please note that my knowledge of calculus of variations is fairly minimal, and I have taken plenty of liberties with rigour.

I'll be more concrete and assume that $P1=(0,0), Q=(.5,.5), P2=(1,0)$; assume the curve is of the form $y=y(x)$ and passes through $P1,P2$ and $Q$ . (Strictly speaking, it should have been $(x(t),y(t))$ to accommodate loops, etc.). Without the pass-through constraint, we would have just set up the Euler Lagrange equations and obtained the following Differential Equation:

$$ \frac{d}{dx} \frac{y'}{\sqrt{1+y'^2}} = 0 (*)$$ subject to $y(0)=0, y(1)=1$.

The pass-through constraint $y(.5) = .5$ cannot be accommodated within the second-order equation above, which admits only two free parameters, supplied by $y(0)$ and $y(1)$. Suppose however that we further differentiate (*), to get :

$$ \frac{d^2}{dx^2} \frac{y'}{\sqrt{1+y'^2}} = 0 (**)$$ subject to $y(0)=0, y(1/2)=1/2, y(1)=1$.

This equation has similar solutions to (*) and admits the pass through constraint as well.

Is the approach shown above valid and extend to multiple intermediate waypoints $Q_1,Q_2..$ ?

Given points $P_1,P_2$ on the plane, how do I find the shortest curve from $P_1$ to $P_2$ that passes through a third point $Q$ (which could be anywhere on the plane) ?

I guess the answer should be the line segments $( P_1Q, P_2Q )$, but how do I properly formulate this as a variational problem? Can the same formulation be extended to multiple intermediate points $Q_1,Q_2,...,Q_n $ in some order?

Note: I couldn't get a good answer to a more non-trivial problem I had in mind at Math.SE at http://bit.ly/ezlMoi, hence this post here. I suppose my original problem is not easily solvable, so I am trying to distil it down to its essence.

Edit : I have a purported answer for the case with a 3rd point $Q$. Suppose that $P_1=(p_{1x}, p_{1y})$ and that $P_2$ and $Q$ have a similar representation. Let's write the curve as $y=y(x)$ ; then the length functional is $L(y) = \int_{p_{1x}}^{p_{2x}} \sqrt{1+y'^2} dx$. Also, since the curve passes through $Q$, it needs to satisfy the condition $C: \min | (x-q_x) (y-q_y)|=0$ as the curve takes on values $(x,y)$. Then the problem reduces to "Minimise $L(y)$ subject to $C$" or to minimising $L(y) + \lambda \min | (x-q_x) (y-q_y)|$. Is this correct?

Given points $P_1,P_2$ on the plane, how do I find the shortest curve from $P_1$ to $P_2$ that passes through a third point $Q$ (which could be anywhere on the plane) ?

I guess the answer should be the line segments $( P_1Q, P_2Q )$, but how do I properly formulate this as a variational problem? Can the same formulation be extended to multiple intermediate points $Q_1,Q_2,...,Q_n $ in some order?

Note: I couldn't get a good answer to a more non-trivial problem I had in mind at Math.SE at http://bit.ly/ezlMoi, hence this post here. I suppose my original problem is not easily solvable, so I am trying to distil it down to its essence.

Edit : I have a purported answer for the case with a 3rd point $Q$. Suppose that $P_1=(p_{1x}, p_{1y})$ and that $P_2$ and $Q$ have a similar representation. Let's write the curve as $y=y(x)$ ; then the length functional is $L(y) = \int_{p_{1x}}^{p_{2x}} \sqrt{1+y'^2} dx$. Also, since the curve passes through $Q$, it needs to satisfy the condition $C: \min | (x-q_x) (y-q_y)|=0$ as the curve takes on values $(x,y)$. Then the problem reduces to "Minimise $L(y)$ subject to $C$" or to minimising $L(y) + \lambda \min | (x-q_x) (y-q_y)|$. Is this correct?

Edit #2 - A new approach I unaccepted Doug's answer below to present my alternative approach. Please note that my knowledge of calculus of variations is fairly minimal, and I have taken plenty of liberties with rigour.

I'll be more concrete and assume that $P1=(0,0), Q=(.5,.5), P2=(1,0)$; assume the curve is of the form $y=y(x)$ and passes through $P1,P2$ and $Q$ . (Strictly speaking, it should have been $(x(t),y(t))$ to accommodate loops, etc.). Without the pass-through constraint, we would have just set up the Euler Lagrange equations and obtained the following Differential Equation:

$$ \frac{d}{dx} \frac{y'}{\sqrt{1+y'^2}} = 0 (*)$$ subject to $y(0)=0, y(1)=1$.

The pass-through constraint $y(.5) = .5$ cannot be accommodated within the second-order equation above, which admits only two free parameters, supplied by $y(0)$ and $y(1)$. Suppose however that we further differentiate (*), to get :

$$ \frac{d^2}{dx^2} \frac{y'}{\sqrt{1+y'^2}} = 0 (**)$$ subject to $y(0)=0, y(1/2)=1/2, y(1)=1$.

This equation has similar solutions to (*) and admits the pass through constraint as well.

Is the approach shown above valid and extend to multiple intermediate waypoints $Q_1,Q_2..$ ?