Geodesics of Length Less Than $\pi R$ in a Set of Reach $R$ Are Unique and Continuous with Respect to the Endpoints

The assumption of positive reach is central to almost all triangulation algorithms, see for example [10, 12, 5], as well as manifold learning, see for example [16, 15, 2, 30]. However these algorithms often consider manifolds of positive reach instead general sets of positive reach. If we want to extend our algorithm beyond the realm of manifolds to more general stratified spaces, starting with “well behaved” sets of positive reach¹¹1Sets of positive reach are stratified spaces [14], where the stratification is understood in a weak sense. However, it is not clear that sets of positive reach are triangulable in general or additional assumptions are needed. This having been said, there are compact sets of (arbitrarily large) positive reach that are not (piecewise smoothly/linearly) homeomorphic to a finite simplicial complex, which puts this outside of the realm of computation. or at least sets of which the strata have positive (local [24]) reach understanding the geometry of those sets seems essential.

Another motivation comes from metric learning. In [1] this is explained as follows:

“In the data analysis area, metric learning refers to the problem of finding a distance $d$ over the space of observations that is relevant for a given task at stake [35, 32]. For instance, in a supervised framework where one is provided with tuples of allegedly similar or dissimilar observations, the goal is to find a distance that is small on the similar tuples and large on the dissimilar ones. There is a wide range of existing methods in the literature, ranging from parametric (LSI [34], MCML [18], LDML [21] among others) to nonparametric (DMLMJ [29], kernel methods [23, 9], to cite a few).

In an unsupervised setting, metric learning aims at finding a metric that takes into account the underlying geometry of the data. That is, it amounts to estimating the shortest-path (or geodesic) distance. Often, this is done via a dimension reduction technique: any low-dimensional embedding of the data gives rise to a new distance over the data in the embedded space. Existing algorithms include PCA, t-SNE [22], MDS [11], Isomap [33], or MVU [4]. See [32] for a thorough overview of the field.”

And indeed in [1] geodesics play a crucial role in establishing optimal bounds.

The terminology $\text{CAT}(k)$ was introduced by Gromov [20] for metric spaces that satisfy some weak form of curvature bound. We’ll now give a rough definition of $\text{CAT}(k)$ spaces, but refer to [7] for a precise introduction, see Section II.1. Let $(ℳ,d_{ℳ})$ be a geodesic metric space, that is a space where the length between two points is defined as the minimum of all lengths of continuous (rectifiable) curves connecting the two points, i.e. the minimum is attained. Such a minimizing curve is called a geodesic. A geodesic triangle in such a space consists of three points and the geodesics connecting those points. We can then consider a geodesic triangle with the same edge lengths in a (simply connected) space of constant curvature $k$ (that is a sphere, Euclidean space, or hyperbolic space). This triangle is called a comparison triangle. We say that the diameter of a simply connected space of constant curvature is $\pi /\sqrt{k}$ if $k>0$ and $\mathrm{\infty }$ otherwise. We also refer to this as the diameter of the comparison space. This geodesic triangle in $ℳ$ satisfies the $\text{CAT}(k)$ inequality if the distances between the points on the triangle are less than the corresponding distances between points on the comparison triangle in a space of constant curvature $k$. If this holds for any geodesic triangle of diameter less than the diameter of the comparison space, then we say that the entire space is $\text{CAT}(k)$.

Lytchak [25, 26] proved sets of positive reach are $\text{CAT}(k)$, for some $k$. Because in (simply connected) spaces of constant curvature, geodesic triangles with small diameter and one edge length equal to zero consist of two coinciding edges, the uniqueness of sufficiently small geodesics follows directly from Lytchak’s result. However, from a computational perspective the result of Lytchak is ineffective, because we only know that such a constant exists and not what this constant may be.

Another way that this paper distinguishes itself compared to the literature, is that the results are all completely elementary, in the sense that we only need some results by Federer [14] and Euler-Lagrange theory [31].

Corollary 3 implies that the geodesic connecting $p$ and $q$ is contained in the intersection of all balls of radius less than the reach that contain $p$ and $q$ so that in particular the geodesic is contained in the spindle (the intersection of all balls of radius $R$ in Euclidean space that contain $p$ and $q$), as depicted in Figure 1. This implies in turn that $|x-{\pi }_{𝒮}(x)|$ less than or equal to the distance from $x$ to the boundary of the spindle. Let’s restrict ourselves to the plane given by $p$, $q$, and ${\pi }_{𝒮}(x)$ and consider a circle of radius $R$ with centre $c$ that yields the boundary of the spindle in this plane, see again Figure 1. By the cosine rule have that

where $\cos \theta =\frac{|p-q|}{2R}$ (the value for $\theta$ follows by inspection of the triangle with vertices $p$, $c$, and $\frac{1}{2}(p+q)$). So that

The first inequality now follows by observing that the distance from $x$ to the spindle is given by $R-|c-\lambda p+(1-\lambda )q|$, see Figure 1. The second inequality follows from the standard observation that $\sqrt{1-t}=1-\frac{t}{2}-𝒪(t^2)$, which in turn follows by Taylor’s theorem. $◀$

We’ll need the following corollary of [14, Theorem 4.8(8)]. Theorem 4.8(8) of [14] says the closest point projection ${\pi }_{𝒮}$ at a point $x$ is $\frac{1}{1-d(x,𝒮)/R}$-Lipschitz. We therefore immediately have:

The following simple but very useful bound will be instrumental in the proof below.

We have that for any two unit vectors $a,b$ that:

and thus

For $a,b$ of arbitrary length we combine (2) and (3) as follows

$◀$

The core idea of the proof is the following: Given two geodesics ${\gamma }_1$ and ${\gamma }_2$ connecting $a,b$ that are parametrized by arc length we have that $\lambda {\gamma }_1+(1-\lambda ){\gamma }_2$ is shorter than ${\gamma }_1$ and ${\gamma }_2$ because , if $\lambda \in (0,1)$. So²²2Here abuse notation a little bit because we do not distinguish the notation for a geodesic and its parametrization. if $\lambda {\gamma }_1+(1-\lambda ){\gamma }_2\subset 𝒮$ we would find a contradiction, because there would be a curve connecting $a$ and $b$ that would be shorter than a geodesic. The main difficulty of the proof is that $\lambda {\gamma }_1+(1-\lambda ){\gamma }_2$ is generally not in $𝒮$, but we need to project on $𝒮$ to find a curve that is. The technical difficulty lies with dealing with this projection.

The proof, perhaps surprisingly, also relies on a result from mathematical physics. Consider the Lagrangian of the (real) harmonic oscillator:

Write $S_{\text{HO}}$ for the action, that is

The Euler-Lagrange equation,

in this case yields

with the familiar solutions $c_1\sin (t/R)+c_2\cos (t/R)=c_4\sin \left(\frac{t-t_0}{R}\right)$. We have the following, see [19, Section V], [28] for this specific result³³3Note that our the Lagrangian of a high dimensional harmonic oscillator (with constant potential) is the sum of one-dimensional harmonic oscillators. and [17] for general theory:

This means in particular that:

Because the geodesic distance between $a$ and $b$ is finite, which means that there exists a path of finite length connecting $a$ and $b$ in $𝒮$. Moreover, thanks to the second paragraph of part III, section 1: “Die Existenz geodätischer Bogen in metrischen Räume” in [27], we have that: If there is at least one path between $a$ and $b$ with finite length, then a minimizing geodesic, i.e. a path with minimal length connecting $a$ to $b$, exists. Therefore the set of minimizing geodesics is not empty.

Let ${\gamma }_1,{\gamma }_2:[0,\mathrm{\ell }]\to S$ be two length minimizing paths from $a$ to $b$, parametrized by arc length, with same length: $\mathrm{length}({\gamma }_1)=\mathrm{length}({\gamma }_2)=\mathrm{\ell }:=d_S(a,b)$.

Denote by $ϵ$ the maximal distance between ${\gamma }_1(t)$ and ${\gamma }_2(t)$, i.e.

and let $t_{\max }\in [0,\mathrm{\ell }]$ be a parameter for this distance is attained, that is,

Without loss of generality, we assume that $t_{\max }\le \mathrm{\ell }/2$.

We now consider the two families of curves

and

We now upper bound the length ${\gamma }_{\lambda }^{𝒮}(t)$. By Lemma 4 we have that

Using Corollary 5 this yields that

We now focus on the second term in the product in the integral.

With Lemma 6 we find the following bound on (6):

Assuming that $(1-\lambda )\lambda$ is very small (more precisely we’ll show that the length decreases in first order near $\lambda =0$ or $\lambda =1$) yields that

Now writing $\mathrm{\Delta }(t)={\gamma }_1(t)-{\gamma }_2(t)$ and thus $\dot{\mathrm{\Delta }}(t)={\dot{\gamma }}_1(t)-{\dot{\gamma }}_2(t)$, this integral (ignoring the higher order terms) takes the form of a familiar Lagrangian integral or action

which we recognize (up to global additive and multiplicative factors) as the action integral of the harmonic oscillator. To achieve better bounds we’ll now split this into two integrals

We’ll only concentrate on the first integral, the second one can be treated in a completely symmetrical manner.

We now invoke Theorem 7 and Corollary 8, with $\tau =\mathrm{\ell }/2$, together with (7), (8), and (9), to find that
$\mathrm{length}({\gamma }_{\lambda }^{𝒮}(t))$ $\le {\displaystyle {\int }_0^{\mathrm{\ell }}}1-{\displaystyle \frac{1}{2}}(1-\lambda )\lambda \left({|{\dot{\gamma }}_1(t)-{\dot{\gamma }}_2(t)|}^2-{\displaystyle \frac{{|{\gamma }_1(t)-{\gamma }_2(t)|}^2}{R^2}}\right)dt$ $+𝒪\left({\lambda }^2{(1-\lambda )}^2\right)$ $=\left({\displaystyle {\int }_0^{\mathrm{\ell }/2}}+{\displaystyle {\int }_{\mathrm{\ell }/2}^{\mathrm{\ell }}}\right)\left(1-{\displaystyle \frac{1}{2}}(1-\lambda )\lambda \left({|{\dot{\gamma }}_1(t)-{\dot{\gamma }}_2(t)|}^2-{\displaystyle \frac{{|{\gamma }_1(t)-{\gamma }_2(t)|}^2}{R^2}}\right)\right)dt$ $+𝒪\left({\lambda }^2{(1-\lambda )}^2\right)$ $\le 2\left(\mathrm{\ell }/2-{\displaystyle \frac{1}{2}}(1-\lambda )\lambda {\displaystyle \frac{c_4^2}{2R}}\sin \left({\displaystyle \frac{\mathrm{\ell }}{R}}\right)\right)+𝒪\left({\lambda }^2{(1-\lambda )}^2\right),$ (the $\le$ follows because $-\frac{1}{2}(1-\lambda )\lambda$ is negative)

where $c_4$ is some constant. This is strictly less than $\mathrm{\ell }$, as long as . This contradicts the assumption that the geodesics have length $\mathrm{\ell }$ (which is the sum of the integral from $0$ to $\mathrm{\ell }/2$ and the integral from $\mathrm{\ell }/2$ to $\mathrm{\ell }$), because now we found a curve that is shorter up to first order. $◀$

Let $a_n$, $b_n$ be a pair of sequences of points in $𝒮$, where ${lim}_{n\to \mathrm{\infty }}{a}_n=a$ and ${lim}_{n\to \mathrm{\infty }}{b}_n=b$, as well as a sequence of geodesics ${\gamma }_n$, connecting $a_n$ and $b_n$. Let $\gamma$ be the minimizing geodesic connecting $a$ and $b$.

We want to prove that ${lim}_{n\to \mathrm{\infty }}{\Vert \gamma -{\gamma }_n\Vert }_{sup}=0$, where $\parallel \cdot {\parallel }_{sup}$ denotes the $C^0$ norm (i.e. sup norm). In other words, we have to prove that, for any $ϵ>0$, the cardinal of the set:

is finite.

Assume to achieve a contradiction that the cardinal of ${\mathrm{\Gamma }}_{ϵ}$ is infinite. Since the set of functions in ${\mathrm{\Gamma }}_{ϵ}$ is bounded and equicontinuous (because they admit a uniform Lipschitz constant), we can apply Arzelà-Ascoli theorem and find a subsequence $\{{\gamma }_{n_k},k\in \mathbb{N}\}\subset {\mathrm{\Gamma }}_{ϵ}$ converging to a curve ${\gamma }^{\prime }$ in $𝒮$. Since $|\text{length}(\gamma )-\text{length}({\gamma }_{n_k})|=|d_{𝒮}(a,b)-d_{𝒮}(a_{n_k},b_{n_k})|\le d_{𝒮}(a,a_{n_k})+d_{𝒮}(b,b_{n_k}).)$ one has ${lim}_{k\to \mathrm{\infty }}\text{length}({\gamma }_{n_k})=\text{length}(\gamma )$.

By a classical result [8, Claim 5.8, page 19], the length of the limit cannot be larger than the limit inf of lengths which yields $\text{length}({\gamma }^{\prime })\le {lim}_{k\to \mathrm{\infty }}\text{length}({\gamma }_{n_k})=\text{length}(\gamma )$. Therefore, ${\gamma }^{\prime }$ would be a geodesic between $a$ and $b$ with ${\Vert \gamma -{\gamma }^{\prime }\Vert }_{sup}\ge ϵ$ which contradicts the unicity of geodesics stated in Theorem 1. $◀$

Corollary 2 has itself another consequence which is worth pointing out.

Write $B_{𝒮}(c,r)$, for the geodesic ball in $𝒮$ with centre $c$ and radius $r$, where . Let $x\in B_{𝒮}(c,r)$, and let ${\gamma }_{xc}(t)$ be the geodesic parametrized by $[0,1]$ with constant arclength with ${\gamma }_{xc}(1)=x$ and ${\gamma }_{xc}(0)=c$. Thanks to Corollary 2 the geodesics are continuous under the $sup$-norm, with respect to endpoint $x$. This means that the map $H:[0,1]\times B_{𝒮}(c,r):(\lambda ,x)\mapsto {\gamma }_{xc}(\lambda )$ is a (continuous) homotopy. $◀$