Extremal curves with a "should pass through" constraint - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T12:51:12Z http://mathoverflow.net/feeds/question/58885 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58885/extremal-curves-with-a-should-pass-through-constraint Extremal curves with a "should pass through" constraint Ganesh 2011-03-18T23:38:44Z 2012-07-28T15:38:37Z <p>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) ?</p> <p>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? </p> <p><b>Note</b>: I couldn't get a good answer to a more non-trivial problem I had in mind at Math.SE at <a href="http://bit.ly/ezlMoi" rel="nofollow">http://bit.ly/ezlMoi</a>, hence this post here. I suppose my original problem is not easily solvable, so I am trying to distil it down to its essence. </p> <p><b> Edit </b>: 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?</p> <p><b> Edit #2 - A new approach </b> 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.</p> <p>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.). <i> Without </i> the pass-through constraint, we would have just set up the Euler Lagrange equations and obtained the following Differential Equation:</p> <p>$$\frac{d}{dx} \frac{y'}{\sqrt{1+y'^2}} = 0 (*)$$ subject to $y(0)=0, y(1)=1$.</p> <p>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 :</p> <p>$$\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$.</p> <p>This equation has similar solutions to (*) and admits the pass through constraint as well. </p> <blockquote> <p>Is the approach shown above valid and extend to multiple intermediate waypoints $Q_1,Q_2..$ ? </p> </blockquote> http://mathoverflow.net/questions/58885/extremal-curves-with-a-should-pass-through-constraint/58924#58924 Answer by Spencer for Extremal curves with a "should pass through" constraint Spencer 2011-03-19T15:20:56Z 2011-03-19T15:20:56Z <p><em><strong>Partial Answer/Too long for comment.</em></strong> 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.</p> <p>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</p> <p>$F(\gamma) = \text{length}(\gamma) + \inf_{x \in (0,1)}|p-q|^2$.</p> <p>You can then calculate the <a href="http://en.wikipedia.org/wiki/Euler%25E2%2580%2593Lagrange_equation#Examples" rel="nofollow">Euler-Lagrange equation</a> for this functional. You do need to justify differentiating through the infimum, though.</p> <p>The more interesting question is that of visiting multiple points in some order. I have not thought about this.</p> http://mathoverflow.net/questions/58885/extremal-curves-with-a-should-pass-through-constraint/103393#103393 Answer by Will Sawin for Extremal curves with a "should pass through" constraint Will Sawin 2012-07-28T15:38:37Z 2012-07-28T15:38:37Z <p>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.</p> <p>So I think it's best to think of it as a series of variational problems with boundary condition.</p> <p>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.</p>