Shortest paths on a manifold with boundary are composed solely of geodesics and boundary sections?

Question

Is the following true?

Proposition: Let $M$ be a manifold with boundary $\partial M$. For any $p, q \in M$ let $P$ be a shortest path from $p$ to $q$. Then $P = \bigcup_{k=1}^n P_k$ where:

1. $P_k$ is a geodesic if $k$ is odd
2. $P_k \subseteq \partial M$ if $k$ is even

My intuition is that the proposition (or something like it with suitable corrections) is well known ... but I haven't been able to find a reference.

Why I am asking

When $M$ is the Euclidean plane and $\partial M$ arises from removing simple polygons, the following Visibility Graph Method can be used to find a shortest path from $p$ to $q$:

1. Locate the vertices $V$ of the polygons
2. Construct the visibility graph $G$ on $V \cup \{ p, q \}$: $x, y$ are adjacent in $G$ if the line segment $xy$ is contained by $M$
3. Search $G$ for a shortest path $P$ from $p$ to $q$

A graph search algorithm (eg Dijkstra's algorithm or A*) will find $P$ as a shortest path in $G$. The Proposition then ensures that $P$ is a shortest path in $M$ from $p$ to $q$.

It is natural to ask about the following generalizations of the Visibility Graph Method:

• $M$ is a 2-manifold and $\partial M$ arises from removing simple polygons where the polygons' edges are geodesics. Here, "line segment $xy$" is replaced with "geodesic $xy$". See for example this question about using visibility graphs to find shortest paths on spheres.

• $M$ is a 2-manifold and $\partial M$ arises from removing simple regions.

(see for example this question about algorithms for finding shortest paths in manifolds).

What I have found so far

The Visibility Graph Method for polyline paths in the plane amidst polygon obstacles is studied in introductions to computational geometry and path planning. See for example de Berg et al (2008) who prove the following:

Lemma 15.1 (de Berg et al, 2008). Any shortest path between a start point and a goal point among a set of $S$ of disjoint polygonal obstacles is a polygonal path whose inner vertices are vertices of $S$. (An inner vertex is a vertex that is neither the begin- nor end-point of the path)

The proof of Lemma 15.1 is that if a path $P$ can be locally shortened then it isn't a shortest path. Hence non-polygonal paths get shortened into polygonal paths, and then they get shortened until the interior vertices are vertices of the polygons.

Outwardly, the proof of Lemma 15.1 resembles the preamble discussion in Pressley (2010, Section 9.4) in which it is established that the shortest path in a surface between two points is always a geodesic. The similarity is in applying local shortening until the path becomes a geodesic.

Consequently for the Proposition, we can at least get to a handwaving proof that (conjecture) the portions of $P$ that are contained in $M - \partial M$ are geodesics.

de Berg et al (2008) then set a exercise for extending to obstacles other than polygons.

Exercise 15.3 (de Berg et al, 2008). Let $S$ be a set of $n$ disjoint disc-shaped obstacles, not necessarily of equal radius. Prove that the shortest path between two points not seeing each other consists of parts of boundaries of the discs, and/or common tangents of discs, and/or tangents from the start or goal point to the discs.

This led me to think that in general (conjecture) shortest paths are composed of geodesics or boundary points.

Alexander & Alexander (1981) proved

Theorem (Alexander & Alexander, 1981). Let $M$ be a Reimannian $C^3$-manifold-with-$C^1$-boundary. A) Any shortest path of $M$ is $C^1$. B) At any point where it touches the boundary, a shortest path of $M$ possesses an osculating plane which is normal to the boundary.

They also commented

If $M$ is a Euclidean space with an open convex body removed, then it is easy to see that a shortest path joining parts of the boundary $\partial M$ must lie in $\partial M$.

The Visibility Graph Method is otherwise not in the mainstream of methods for finding shortest paths on surfaces. See for example Bose et al (2011), Crane et al (2020). There appear to be two reasons: the geodesics are not easy to obtain (except in special cases such as the Euclidean plane or the sphere - see for example this question on the kind of computations that are needed generally), and the feeling that the visibility graph is too large to work with.

References

de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried. (2008). Computational geometry. Algorithms and applications: Third Edition., Berlin: Springer.

Pressley, Andrew. (2010). Elementary Differential Geometry: Second Edition, Springer Undergraduate Mathematics Series. London: Springer-Verlag. DOI 10.1007/978-1-84882-891-9_9

Alexander, Ralph; Alexander, S. (1981) Geodesics in Riemannian manifolds-with-boundary, Indiana Univ. Math. J. 30, 481-488. ZBL0469.53039.

Bose, Prosenjit; Maheshwari, Anil; Shu, Chang; Wuhrer, Stefanie. (2011) A survey of geodesic paths on 3D surfaces, Comput. Geom. 44, No. 9, 486-498 ZBL1231.65038.

Crane, Keenan; Livesu, Marco; Puppo, Enrico; Qin, Yipeng. (2020) A Survey of Algorithms for Geodesic Paths and Distance Maps. ArXiV 2007.10430

Answer 1

In order to correct my comment:

1. First, assume that $M$ has $C^\infty$ boundary. Then, in general, it is false that length-minimizers in $M$ (between points in $M$) are concatenations of finitely many geodesics in $M$ and paths in $\partial M$. The simplest example I know, is to take a $C^\infty$-function $f\ge 0$ defined on the real line such that $f^{-1}(0)$ equals to, say, $$ A= \{0\}\cup \{n^{-1}: n\in {\mathbb N}\}. $$ (Or, if you prefer, the Cantor set.)

Now, let $M$ denote the subgraph of $f$, i.e. $$ M=\{(x,y): y\le f(x)\}\subset {\mathbb R}^2. $$ I will equip $M$ with the restriction of the standard (flat) Riemannian. metric on the plane. Then for $p=(0,0), q=(1,0)$ the minimizing path is the unit interval in the $x$-axis and, by the construction, it intersects the boundary of $M$ in the subset $A\times \{0\}$.

2. On the other hand, suppose that $M$ is a surface with piecewise-geodesic boundary (I think, this is the case you are actually interested in). Then, indeed, each length-minimizer (connecting two points of $M$) is a finite concatenation as required.

Proof. Suppose that $c: I=[a,b]\to M$ is our length-minimizer. Then $A=c^{-1}(\partial M)$ is a closed subset of $I$; let $B$ denote its complement. If $A$ is a finite union of closed intervals, we are done. Suppose not. Then there exists a converging sequence $t_i\in \partial A$ such that for all $t_i< t_j$, the interval $[t_i, t_j]$ is not contained in $A$. Since $\partial M$ is a finite union of geodesic segments, after further extraction, we can assume that all the member of the sequence $c(t_i)$ belong to the same geodesic segment $\alpha\subset \partial M$ and, moreover, belong to a totally normal neighborhood $U$ of the limit point $c(t)$, where $t=\lim_i t_i$. However, by the total normality assumption, $U\cap \alpha$ is distance-minimizer in $M$. Since $c(t_i), c(t_j)$ are in $\alpha\cap U$ and $c$ is a minimizing path, it follows that $c([t_i, t_j])\subset \alpha$ (whenever $t_i< t_j$). But this contradicts the property that $[t_i, t_j]$ is not contained in $A$. qed