Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
The second (curvature) version of your problem on SE hardly makes sense without additional restrictions: just go in huge "almost circles" swooping one point a time. The first one is the classical traveling salesman problem on the plane. It is easier than the general version but still hard to solve exactly. Look up "Barvinok"+"traveling salesman"+"Euclidean" on Google or ArXiV for approximate polynomial time solutions. –  fedja Mar 19 '11 at 0:44
    
Right, from a programmer's perspective it's a dynamic programming problem. However, I'm more interested in the <i>formulation </i> of the problem, and trying to extend this to functionals that may not be possibly additive. –  Ganesh Mar 19 '11 at 0:47
    
@ fedja: Won't the huge "almost circles" [ whatever that might be] lead to a big increase in length? –  Ganesh Mar 19 '11 at 0:50
    
I deleted my first comment; sorry, I did not get that you were only interested in the formulation. –  quid Mar 19 '11 at 1:04
    
@Ganesh: Of course, but you have either to choose one or the other, or to tell exactly how you weigh the two. You cannot have them at their minima simultaneously. –  fedja Mar 24 '11 at 11:56
show 1 more comment

2 Answers 2

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.

share|improve this answer
    
Thanks. Can't we extend this for multiple $q$'s, by having $F(\gamma)= length(\gamma) + \sum inf_{x} |p-q_i|^2$ ? And under what conditions can we differentiate through the infimum? –  Ganesh Mar 23 '11 at 23:11
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.