Extremal curves with a "should pass through" constraint - MathOverflow

Extremal curves with a "should pass through" constraint

2011-03-18T23:38:44Z

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..$ ?

Answer by Spencer for Extremal curves with a "should pass through" constraint

2011-03-19T15:20:56Z

Partial Answer/Too long for comment. If you are just working in the plane, then intuitively you know already that a length-minimizer exists (so long as you allow self-intersections). Such a solution will be a geodesic. This means you know (ahead of designing your functional) that a solution won't have any curvature - so one ought to focus on the length minimzation.

From here, it seems to me (I have not done any detailed calculation) that some sort of reasonable convex penalization on your curves for not going through a given point $q$ will result in the right critical points. For example, if you work in a class of piecewise $C^1$ curves $\gamma :(0,1) \to \mathbb{R}^2$, then consider

$F(\gamma) = \text{length}(\gamma) + \inf_{x \in (0,1)}|p-q|^2$.

You can then calculate the Euler-Lagrange equation for this functional. You do need to justify differentiating through the infimum, though.

The more interesting question is that of visiting multiple points in some order. I have not thought about this.

Answer by Will Sawin for Extremal curves with a "should pass through" constraint

2012-07-28T15:38:37Z

A curve from $P_1$ to $P_2$ which passes through $Q$ is a curve from $P_1$ to $Q$ followed by a curve from $Q$ to $P_2$. Similarly for multiple intermediate points.

So I think it's best to think of it as a series of variational problems with boundary condition.

For your other problem: I would formulate it like this: Find the minimum length for a curve of curvature bounded above by a constant that passes through two points $P_1$ and $P_2$ with a fixed slope at $P_1$ and a fixed slope at $P_2$. Then you can glue a bunch of these curves together and optimize the slopes.