Find the shortest path enclosed by two functions.

Question

Let $f, g : [a, b] \to \mathbb{R}$ be two continuous functions such that $$f(x)<g(x)\ \ \forall\ x\in(a,b)$$

Let $P_1\ (x_1,\ y_1)$ and $P_2\ (x_2,\ y_2)$ such that $$a \le x_1, x_2\le b\ ,\\ \ \ \ \ \ \ \ \ f(x_1) < y_1 < g(x_1)\ and\\ f(x_2) < y_2 < g(x_2)$$

Describe a general way to find the shortest (in length) continuous function $h$ that connects the two points and $$f(x)<h(x)<g(x)\ \ \forall\ x\in[x_1,x_2]$$ Notes

1. You may also consider the case $$f(x)\le h(x)\le g(x)$$ and (optionally): $$\ \ \ \ \ \ \ \ f(x_1) \le y_1\le g(x_1)\ and\\ f(x_2) \le y_2\le g(x_2)$$

2. You may make any extra necessary assumptions (e.g. differentiability) provided that the problem does not become trivial.

(Edit 6:)

3. If you already know the answer telling me which topics I should look into is enough (and you probably don't need to read further).

(Edit 4:)

Comment

Proposed solution (by Christian Blatter):

"Stretch a rubber band from P1 to P2. This band will be straight whenever it does not lie along one of the boundary curves."

If this statement is true, I would very much like to see a proof.

(Edit 7:)

(Pointed out by TonyK) There's not always a function that satisfies the original argument (not the things in the Notes section). There may only be an infimum for the length of $h$.

(Edit 5:)

How the problem arose

I was walking on the street which was formed by the arcs of two concentric circles. I was trying to find what trajectory I should follow so that walking "a given angle" around the circle and simultaneously "crossing the street" I would walk the least. If the line that connects the two points is on the street then problem is trivial. If not I should either:

1. Follow the obvious tangent from $P_1$ to the small circle, walk as much as necessary on this circle to "find" the tangent from this circle to the other point etc. Or
2. I should move in such a way so the distance between me and the center of the circles changes at some rate (possibly constant) making a spiral like path.

Until now I don't know which option is the best.

The original question is more general. The problem can be generalized even further of course. For example one could consider instead of the functions f, g a set of points. Also the problem can be extended in higher dimensions.

To save time

The post has been edited to include the useful comments made to it. You may skip reading them. However, I encourage you to look at the attempted answers and their comments.

Answer 1

Here is my attempt at making a claim and proving it. Essentially it is "be as close to the straight line connecting $P_1$ and $P_2$ as possible"

Claim: Denote the line segment from $P_1$ to $P_2$ by $L$. Then the continuous function $h$ on $[x_1 , x_2]$ given by $$ h(x) = \begin{cases} L(x) & \mbox{ if } f(x) < L(x) < g(x) \\ f(x) & \mbox{ if } L(x) \leq f(x) \\ g(x) & \mbox{ if } L(x) \geq g(x) \end{cases} $$ is the shortest continuous path connecting $P_1$ to $P_2$ such that $f \leq h \leq g$

The general case for $h$ follows from the cases below.

If $h(x)=L(x)$ for all $x \in [x_1 , x_2 ]$, then we are done since the shortest path between two points is the line segment joining them

Assume WLOG that that $h(x) > L(x)$ for some $x$, and $h \leq g$ (if we flip the inequality directions and replace $g$ with $f$, the proof is equivalent just "upside down"). But assume by way of contradiction that there exists a continuous function $H$ satisfying the problem such that $H \neq h$ and the arc length of $H$ on $[x_1 , x_2]$ is less than that of $h$. Then $$ H \geq h \geq L $$ and there $\exists x$ such that $$ H(x) > h(x) $$ These facts show that $H$ "deviates" strictly more than $h$ from $L$ (which is the shortest possible path). Actually we can approximate $h$ by a polygonal path $\gamma_n$ and $H$ by a polygonal path $\Gamma_n$, where $n$ is the number of line segments in the polygonal path, such that $h(x) \in \gamma_n$ and $H(x) \in \Gamma_n$. Then $$ \lim_{n \to \infty} \gamma_n = h $$ $$ \lim_{n \to \infty} \Gamma_n = H $$ and $$ arclength(\gamma_n) < arclength(\Gamma_n) \quad \forall n>1 $$ From these 3 facts we conclude $$ arclength(h) < arclength(H) $$ as desired as it completes the contradiction

Answer 2

I assume the boundary functions are differentiable.

If the path goes through any two points in the strict region between the two functions (yellow, below), it must do so in a straight line (of course), as that's the shortest distance between those points.

Any other section of a path must include sections along the boundary functions themselves.

The touching of such sections must occur at a point where the straight line is tangent to the boundary function, otherwise you could replace that section with a shorter segment that is tangent (see second figure).

Hence the solution is an alternating path of straight segments tangent to the boundary functions, then sections of the boundary functions, as shown here:

This is indeed the "rubber band" solution, but the previous answerer did not stress the key fact that the rubber band must touch a boundary curve as a tangent.

To see that the tangent transition is always shortest, just study this figure and compare the red and green paths between the two black points:

Answer 3

$\def\m{\mu}$What follows is a sketch of a solution using the calculus of variations.

Consider $h(x)$ for $x\in[a,b]$ such that $f(x)\le h(x)\le g(x)$ where $(a,h(a))$ and $(b,h(b))$ are given. We wish to minimize $$\int_a^b \sqrt{1+h'(x)^2}dx$$ with respect to $h(x)$ subject to the above constraints.

We introduce Lagrange multipliers $\m_1(x),\m_2(x)\ge 0$ to impose the constraints $f(x)\le h(x)$ and $h(x)\le g(x)$ and instead extremize $$d(h(x),\m_1(x),\m_2(x)) = \int_a^b\left[ \sqrt{1+h'(x)^2} + \m_1(x)(f(x)-h(x)) + \m_2(x)(h(x)-g(x)\right]dx.$$ We maximize $d$ with respect to $\m_1(x)$ and $\m_2(x)$ and minimize with respect to $h(x)$. Below we consider how the first constraint is imposed by this choice. The second constraint can be understood similarly.

When the first constraint is satisfied but not active, $f(x)<h(x)$ or $f(x)-h(x)<0$, we have $\m_1(x)=0$. (We maximize with respect to $\m_1$ and $\m_1(x)(f(x)-h(x))\le0$. Thus, $\m_1(x)=0$.)

When the first constraint is satisfied and active, $f(x)=h(x)$, then $\m_1(x)\ge0$.

When the first constraint is not satisfied, $f(x)>h(x)$, then $\m_1(x)\rightarrow\infty$ and so $d\rightarrow\infty$. Thus, the length of the path will not be minimized when the constraint is not satisfied.

Varying with respect to $h(x)$, $\m_1(x)$ and $\m_2(x)$, we find \begin{align*} \frac{h''(x)}{(1+h'(x)^2)^{3/2}} &= \m_2(x)-\m_1(x) \tag{1} \\ h(x) &= f(x), & \textrm{unless $\m_1(x)=0$} \\ h(x) &= g(x). & \textrm{unless $\m_2(x)=0$} \end{align*} In a region for which the constraint is satisfied and not active we find $h''(x) = 0$. Thus, $h(x)$ is a straight line in this region. Otherwise, when the constraint is satisfied and active, we have that $h(x)$ is given by either $f(x)$ or $g(x)$. In a region where the first constraint is satisfied and not active we have $\m_1(x)=0$. In a region where the first constraint is satisfied and active we have $\m_1(x) = -f''(x)/(1+f'(x)^2)^{3/2}$. Assuming that $f''(x)$ is piecewise continuous we find that $\m_1(x)$ is at worst piecewise continuous. (Similar remarks can be made for $\m_2$ and $g$.) Integrating both sides of (1) over a generic infinitesimal region, we find that $h'(x)$ must be continuous. Thus, to find the optimal path we find the shortest differentiable path consisting of straight line segments and subsets of the graphs of $f$ and $g$ between the two points in question.

Answer 4

$\def\e{\varepsilon} \def\vu{{\bf u}} \def\vv{{\bf v}} \newcommand\comp[1]{\langle #1\rangle} \def\c{\xb^*} \def\cc{c'} \def\m{\mu} \def\pa{P_1} \def\xa{x_1} \def\ya{y_1} \def\pb{P'} \def\xb{c} \def\yb{f(\xb)} \def\pc{P_2} \def\xc{x_2} \def\yc{f(\xc)}$Here we prove a claim in the answer by @DavidG.Stork's that the "tangent transition" gives the shortest path.

Let $\pa=\pa(\xa,\ya)$, $\pb=(\xb,f(\xb))$, and $\pc=(\xc,f(\xc))$. Assume that $\xa\ne \xc$, $\xa\le \xb\le \xc$, and $\ya>f(\xa)$.
Define $$h(x;\xb) = \begin{cases} L(x;\xb), & \xa\le x< \xb \\ f(x), & \xb\le x\le \xc, \end{cases}$$ where $L(x;\xb)=\ya+\frac{f(\xb)-\ya}{\xb-\xa}(x-\xa)$. Thus, $(x,h(x;\xb))$ for $x\in[\xa,\xc]$ is the curve consisting of the line segment from $\pa$ to $\pb$ and the path from $\pb$ to $\pc$ along the curve determined by $f$. The curve specified by $h(x;\xb)$ is admissible if $h(x;\xb)\ge f(x)$ for $x\in[\xa,\xc]$, that is, if $L(x;\xb)\ge f(x)$ for $x\in[\xa,\xb]$. We assume that $f$ is differentiable on $[\xa,\xc]$. See Figure 1 below.

The length the path is $$d(\xb) = \sqrt{(\xb-\xa)^2+(f(\xb)-\ya)^2} +\int_{\xb}^{\xc}\sqrt{1+f'(t)^2}dt.$$ Thus, $$d'(\xb)=\frac{\xb-\xa+(f(\xb)-\ya)f'(\xb)}{\sqrt{(\xb-\xa)^2+(f(\xb)-\ya)^2}} - \sqrt{1+f'(\xb)^2}.$$ The critical points are given by the $\xb=\c\in(\xa,\xc)$ such that $d'(\c)=0$. Let $\vu=\comp{\xb-\xa,f(\xb)-\ya}$ and $\vv=\comp{1,f'(\xb)}$. Then $d'(\xb) = \left(\vu\cdot\vv-|\vu||\vv|\right)/|\vu|.$ Note that $d'(\xb)=0$ only if $\vu=\alpha\vv$ for some $\alpha>0$. This immediately implies that $$f'(\c) = \frac{f(\c)-\ya}{\c-\xa}$$ for any $\c$ such that $d'(\c)=0$. Thus, $h(x;\c)$ is differentiable, that is, the line through $\pa$ and $\pb(\c,f(\c))$ is tangent to the curve determined by $f$ at $x=\c$. See Figures 2 and 5 below.

By the Cauchy-Schwarz inequality, $$d'(\xb)\le 0.$$ Naively, we may have expected to find a local minimum for $d$, but instead we have that $d$ decreases as we approach $\c$ and then decreases further as we pass by $\c$. To understand this, consider $L(x;\c)-f(x)$ near $x=\c$. We find $L(x;\c)-f(x) = -\frac{1}{2}f''(\c)(x-\c)^2+O((x-\c)^3)$. Assuming that $f''(\c)\ne0$, this implies that $f''(\c)< 0$. (Otherwise the curve would not be admissible.)
Further, note that $L(\c;\c+\e)-f(\c) = \frac{1}{2}f''(\c)\e^2+O(\e^3)<0$ for $\e>0$ sufficiently small. This implies that curves corresponding to $h(x;c)$ for $c\in(\c,\c+\e)$ are not admissible. See Figure 3 below.

Thus, disregarding admissibility, $d$ is a nonincreasing function of $\xb$ for which $d'(\xb)=0$ only if the slopes of $L(x;\xb)$ and $f(x)$ agree at $\xb$. By requiring only admissible paths we can see that $d$ is a nonincreasing function with regions corresponding to nonadmissible paths removed. These regions will be of the form $(\c,\cc)$, where $\cc$ is the smallest $\xb\in(\c,\xc)$ such that $L(\cc;\xb)=f(\cc)$, if such an $\cc$ exists. (If not, the region is $(\c,\xc)$.) See Figure 4 below.

If $f(x)\le L(x;\xc)$ for all $x\in[\xa,\xc]$, then the shortest path is given by $L(x;\xc)$. If $f(x)>L(x;\xc)$ for some $x\in[\xa,\xc]$ then, by the mean value theorem, there will be a $\c\in(\xa,\xc)$ such that $f'(\c)=0$. Let $\{\c_i\}$ be the collection of such values. Since $d$ is nonincreasing, the shortest path with be given by $h(x;c)$, where $c$ is the largest member of this set.
Thus, to minimize $d$ we choose a straight line between $\pa$ and $\pc$ if possible, otherwise we choose the "furthest" tangent transition. See Figure 6 below.