# Metric and Path-Connectedness Properties of the Fréchet Distance for Paths
and Graphs

Erin Chambers Department of Computer Science, Saint Louis University,
<EMAIL_ADDRESS>Brittany Terese Fasy School of Computing, Department of
Mathematics, Montana State University<EMAIL_ADDRESS>Benjamin
Holmgren School of Computing, Montana State University
<EMAIL_ADDRESS>Sushovan Majhi School of Information,
University of California, Berkeley<EMAIL_ADDRESS>Carola Wenk
Department of Computer Science, Tulane University<EMAIL_ADDRESS>
###### Abstract

The Fréchet distance is often used to measure distances between paths, with
applications in areas ranging from map matching to GPS trajectory analysis to
hand-writing recognition. More recently, the Fréchet distance has been
generalized to a distance between two copies of the same graph embedded or
immersed in a metric space; this more general setting opens up a wide range of
more complex applications in graph analysis. In this paper, we initiate a
study of some of the fundamental topological properties of spaces of paths and
of graphs mapped to $\mathbb{R}^{n}$ under the Fréchet distance, in an effort
to lay the theoretical groundwork for understanding how these distances can be
used in practice. In particular, we prove whether or not these spaces, and the
metric balls therein, are path-connected.

##  1 Introduction

One-dimensional data in a Euclidean ambient space is heavily studied in the
computational geometry literature, and is central to applications in GPS
trajectory and road network analysis [2, 11, 13, 24]. One widely used distance
measure on one-dimensional data is the Fréchet distance, which accounts for
both geometric closeness as well as the connectivity of the paths or graphs
being compared [21, 20, 7, 8, 10, 4, 6, 1, 17, 5, 16, 22, 12, 18, 11, 14, 13].
We build a theoretical foundation for these application areas by investigating
spaces of paths and graphs in $\mathbb{R}^{n}$, including their metric and
topological properties, under the Fréchet distance. The motivation for this
work is simple: as practical approaches to compute the Fréchet distance
between paths [6, 14] and between graphs [18, 20, 10] grow in popularity, it
is natural to inquire about the fundamental properties of such distances, in
an effort to better understand exactly what they are capturing.

We begin by defining the Fréchet distance between paths and graphs. Using open
balls under the Fréchet distance to generate a topology, we study the metric
and topological properties of the induced spaces. In particular, we work with
three classes of paths: the space $\Pi_{\mathcal{C}}$ of all paths in
$\mathbb{R}^{n}$, the space $\Pi_{\mathcal{E}}$ of all paths in
$\mathbb{R}^{n}$ that are embeddings (i.e., maps that are homeomorphisms onto
the image), and the space $\Pi_{\mathcal{I}}$ of all paths in $\mathbb{R}^{n}$
that are immersions (local embeddings). See Figure 1 for examples of paths in
$\mathbb{R}^{2}$. In addition, we study the three analogous spaces of graphs:
the sets $\mathcal{G}_{\mathcal{C}}$, $\mathcal{G}_{\mathcal{I}}$, and
$\mathcal{G}_{\mathcal{E}}$ of continuous maps, immersions, and embeddings of
graphs, respectively. This paper establishes the core metric and topological
properties of the Fréchet distance on graphs and paths in Euclidean space.

(a) Continuous

(b) Embedding

(c) Immersion

Figure 1: Example of paths continuously mapped, embedded, and immersed in
$\mathbb{R}^{2}$. The space of continuous maps allows arbitrary self-
intersection on a path including backtracking (which occurs at the two red
points); embeddings must induce homeomorphisms onto their image; and
immersions are locally embeddings.

##  2 Background

In this section, we establish the definitions and notation from geometry and
topology used throughout. We assume basic knowledge of concepts in topology.
For common definitions central to this paper, we refer readers to Appendix A,
or for greater detail, to [19, 9].

######  Definition  (Types of Maps)

Let $\mathbb{X}$ and $\mathbb{Y}$ be topological spaces. A map
$\alpha\colon\mathbb{X}\to\mathbb{Y}$ is called _continuous_ if for each open
set $U\subset\mathbb{Y}$, $\alpha^{-1}(U)$ is open in $\mathbb{X}$. We call
$\alpha$ an _embedding_ if $\alpha$ is injective. Equivalently, an _embedding_
is a continuous map that is homeomorphic onto its image. If $\alpha$ is
locally an embedding, then we say that $\alpha$ is an  _immersion_.

In particular, a continuous map $\gamma\colon[0,1]\to\mathbb{R}^{n}$ is called
a _path_ in $\mathbb{R}^{n}$. We call a path
$\gamma\colon[0,1]\to\mathbb{R}^{n}$ _rectifiable_ if $\gamma$ has finite
_length_ (see Definition A.9 in Appendix A.3). Moreover, we call a graph $G$
rectifiable if there exists a finite cover of $G$ such that every element in
the cover is a rectifiable path.

#### Paths in $\mathbb{R}^{n}$

Letting $\widetilde{\Pi_{\mathcal{C}}}$ denote the set of all rectifiable
paths in $\mathbb{R}^{n}$, we now define the path Fréchet distance.

######  Definition  (The Path Fréchet Distance [4])

The _Fréchet distance_
$d_{FP}\colon\widetilde{\Pi_{\mathcal{C}}}\times\widetilde{\Pi_{\mathcal{C}}}\to\bar{\mathbb{R}}_{\geq
0}$ between $\gamma_{1},\gamma_{2}\in\widetilde{\Pi_{\mathcal{C}}}$ is defined
as:

$d_{FP}(\gamma_{1},\gamma_{2}):=\inf_{r\colon[0,1]\to[0,1]}\max_{t\in[0,1]}||\gamma_{1}(t)-\gamma_{2}(r(t))||_{2},$

where $r$ ranges over all homeomorphisms such that $r(0)=0$, and
$||\cdot||_{2}$ denotes the Euclidean norm.

#### Graphs Mapped to $\mathbb{R}^{n}$

We define a _graph_ $G=(V,E)$ as a finite set of vertices $V$ and a finite set
of edges $E$. Self-loops and multiple edges between a pair of vertices are
allowed.111Some references would call this a _multi-graph_ , but for
simplicity, we just use the term _graph_. We topologize a graph by thinking of
it as a CW complex; see Appendix A.1. If $\phi\colon G\to\mathbb{R}^{d}$ is a
map, then we call $(G,\phi)$ a graph-map pair. We extend the path Fréchet
distance to the Fréchet distance between graphs continuously mapped into
$\mathbb{R}^{n}$:

######  Definition  (Graph Fréchet Distance)

Let $(G,\phi),(H,\psi)$ be continuous, rectifiable graph-map pairs. We define
the Fréchet distance between $(G,\phi)$ and $(H,\psi)$ by minimizing over all
homeomorphisms:222Other generalizations of the Fréchet distance minimize over
all “orientation-preserving” homeomorphisms, which can be defined in several
ways for stratified spaces, and sometimes adding an orientation is not
natural. Thus, we drop this requirement in our definition.

$d_{FG}\left((G,\phi),(H,\psi)\right):=\begin{cases}\inf_{h}||\phi-\psi\circ
h||_{\infty}&G\cong H.\\\ \infty&\text{otherwise}.\\\ \end{cases}$

For simplicity of exposition, when $G\cong H$, we write the LHS of this
equation as $d_{FG}(\phi,\psi)$. Furthermore, defining the infimum over an
emptyset to be $\infty$, the graph Fréchet distance is given by the following
equation:

$d_{FG}\left((G,\phi),(H,\psi)\right):=\inf_{h}||\phi-\psi\circ h||_{\infty},$

where the infimum is taken over all homeomorphisms $h\colon G\to H$.

Note that if $G=H$ and $\phi$ is a reparameterization of $\psi$, then
$d_{FG}(\phi,\psi)=0$.

[Paths as Graphs] If $G=[0,1]$ and $\alpha,\beta\colon[0,1]\to\mathbb{R}^{n}$
are paths, then the relationship between path and graph Fréchet distances is
as follows:

$d_{FG}\left(\alpha,\beta\right)=\min\left\\{d_{FP}(\alpha,\beta),d_{FP}(\alpha,\beta^{-1})\right\\},$

where $\beta^{-1}\colon I\to\mathbb{R}^{n}$ is defined by
$\beta^{-1}(t)=\beta(1-t)$.

##  3 Metric Properties

We now address the question: Is this distance a metric? If not, can it be
metrized? A well-known known property of the path Fréchet distance is that it
is a pseudo-metric [21, 4]. That is, it satisfies all metric properties except
for separability. We proof this property for $d_{FG}$.

######  Theorem 3.1 (Metric Properties of $d_{FG}$).

$d_{FG}$ is an extended pseudo-metric that does not satisfy separability. When
restricted to a homeomorphism class of graphs, $d_{FG}$ is a pseudo-metric.

######  Proof 3.2.

We first prove that $d_{FG}$ is an extended pseudo-metric (see Definition A.4
in Appendix A.3).

Identity: Taking $h$ to be the identity map in Definition 2, we find
$d_{FG}((G,\phi_{1}),(G,\phi_{1}))=0$.

Symmetry: Consider $d_{FG}(\phi_{1},\phi_{2})$. If $G\not\cong H$, then no
homeomorphism $h\colon G\to H$ exists. Likewise, no homeomorphism
$h^{\prime}\colon H\to G$ exists. And, so,

$d_{FG}((G,\phi_{1}),(H,\phi_{2})))=\infty=d_{FG}((H,\phi_{2}),(G,\phi_{1}))).$

Otherwise, since $h$ is a homeomorphism, it is invertible. Thus, we can
rewrite this as:

$d_{FG}(\phi_{1},\phi_{2})=\underset{h^{-1}}{\inf}||\phi_{1}\circ
h^{-1}-\phi_{2}||_{\infty}=d_{FG}(\phi_{2},\phi_{1}).$

Subadditivity (the triangle inequality): Consider
$d_{FG}((G_{1},\phi_{1}),(G_{2},\phi_{2}))+d_{FG}((G_{2},\phi_{2}),(G_{3},\phi_{3}))$.
If $G_{1}\not\cong G_{2}$, then
$d_{FG}((G_{1},\phi_{1}),(G_{2},\phi_{2}))=\infty$, and we are done. A
symmetric argument follows for $G_{2}\not\cong G_{3}$. Thus, we assume
$G_{1}\cong G_{2}\cong G_{3}$. Using the definition of Fréchet distance and
the fact that the infimum is taken over homeomorphisms, we obtain:

$\displaystyle d_{FG}(\phi_{1},\phi_{2})+d_{FG}(\phi_{2},\phi_{3})$
$\displaystyle\qquad=\inf_{h^{\prime}}||\phi_{1}-\phi_{2}\circ
h^{\prime}||_{\infty}+\inf_{h^{\prime\prime}}||\phi_{2}-\phi_{3}\circ
h^{\prime\prime}||_{\infty}.$
$\displaystyle\qquad\geq\inf_{h^{\prime}}||\phi_{1}-\phi_{2}\circ
h^{\prime}||_{\infty}+\inf_{h,h^{\prime}}||\phi_{2}\circ
h^{\prime}-\phi_{3}\circ h||_{\infty}$
$\displaystyle\qquad=\inf_{h,h^{\prime}}||\phi_{1}+(\phi_{2}\circ
h^{\prime}-\phi_{2}\circ h^{\prime})-\phi_{3}\circ h||_{\infty}$
$\displaystyle\qquad=\inf_{h}||\phi_{1}-\phi_{3}\circ h||_{\infty}$
$\displaystyle\qquad=d_{FG}(\phi_{1},\phi_{3}).$

And so, we conclude that $d_{FG}$ satisfies subadditivity.

Noting that if $G\not\cong H$ that
$d_{FG}\left((G,\phi),(H,\psi)\right)=\infty$, we conclude that $d_{FG}$ is an
extended pseudo-metric. However, the graph Fréchet distance between
homeomorphic graphs is at most the Hausdorff distance between the images of
the two maps. Thus, when restricted to a homeomorphism class of graphs,
$d_{FG}$ is a pseudo-metric.

The only metric property not satisfied is separability. In order to metrize
this pseudo-metric, we define $\mathcal{G}_{\mathcal{C}}(G)$ to be the the set
of equivalence classes of continuous, rectifiable maps $G\to\mathbb{R}^{n}$,
where two maps, $\phi_{1}$ and $\phi_{2}$, are equivalent if and only if
$d_{FG}(\phi_{1},\phi_{2})=0$. We write $[\phi_{i}]$ to denote the equivalence
class of maps containing $\phi_{i}$. We define two subspaces of
$\mathcal{G}_{\mathcal{C}}(G)$: those representing immersions and embeddings,
denoted $\mathcal{G}_{\mathcal{I}}(G)$ and $\mathcal{G}_{\mathcal{E}}(G)$,
respectively. Note that
$\mathcal{G}_{\mathcal{E}}(G)\subsetneq\mathcal{G}_{\mathcal{I}}(G)\subsetneq\mathcal{G}_{\mathcal{C}}(G)$.
Let $\mathcal{G}_{\mathcal{C}}$ denote the induced set of equivalence classes
of all graph-map pairs $(G,[\phi])$ such that
$[\phi]\in\mathcal{G}_{\mathcal{C}}(G)$. Similiarly, we define
$\mathcal{G}_{\mathcal{I}}$ and $\mathcal{G}_{\mathcal{E}}$, and note
$\mathcal{G}_{\mathcal{E}}\subsetneq\mathcal{G}_{\mathcal{I}}\subsetneq\mathcal{G}_{\mathcal{C}}$.
Hence,

######  Corollary 1 (Metric Extension for Graphs).

For every graph $G$, the graph Fréchet distance is a metric on the quotient
spaces $\mathcal{G}_{\mathcal{C}}(G)$, $\mathcal{G}_{\mathcal{I}}(G)$, and
$\mathcal{G}_{\mathcal{E}}(G)$. Moreover, the graph Fréchet distance is an
extended metric on $\mathcal{G}_{\mathcal{C}}$, $\mathcal{G}_{\mathcal{I}}$,
and $\mathcal{G}_{\mathcal{E}}$.

Similarly, we consider paths in $\mathbb{R}^{n}$: in particular,
$\Pi_{\mathcal{C}}$ is the set of equivalences classes of
$\widetilde{\Pi_{\mathcal{C}}}$ up to orientation-preserving
reparameterization. Equivalently, for
$\gamma_{1},\gamma_{2}\in\widetilde{\Pi_{\mathcal{C}}}$, $\gamma_{1}$ is
equivalent to $\gamma_{2}$ iff $d_{FP}(\gamma_{1},\gamma_{2})=0$. Likewise,
$\Pi_{\mathcal{E}}$ and $\Pi_{\mathcal{I}}$ are the subspaces of embeddings
and immersions. Note that
$\Pi_{\mathcal{E}}\subsetneq\Pi_{\mathcal{I}}\subsetneq\Pi_{\mathcal{C}}$. We
topologize these spaces using the open ball topology (Appendix A.3). Again, by
construction, we obtain:

######  Corollary 2 (Metric Properties of $d_{FP}$).

The path Fréchet distance is a metric on $\Pi_{\mathcal{C}},\Pi_{\mathcal{I}}$
and $\Pi_{\mathcal{E}}$.

##  4 Path-Connectedness Property

We now examine path-connectedness properties. See Definition A.7 and
Definition A.8 of Appendix A.4 for definitions of path-connectivity.

###  4.1 Continuous Mappings

We start with the most general spaces of paths and graphs: the continuous,
rectifiable maps into $\mathbb{R}^{n}$. In Euclidean spaces, linear
interpolation is a useful tool because it defines the shortest paths between
two points. In function spaces, linear interpolation is also nice:

######  Definition 4.1 (Linear Interpolation).

Let $G$ be a graph and $\phi_{0},\phi_{1}\colon G\to\mathbb{R}^{n}$ be
continuous, rectifiable maps. The _linear interpolation_ from $\phi_{0}$ to
$\phi_{1}$ is the map $\Gamma\colon[0,1]\to\mathcal{G}_{\mathcal{C}}(G)$
sending $t\in[0,1]$ to $(G,\phi_{t})$, where:

$\phi_{t}:=(1-t)\phi_{0}+t(\phi_{1}\circ h_{*}).$ (1)

For ease of notation, we sometimes write $\Gamma_{t}:=\Gamma(t)$.

Note that $(1-t)\phi_{0}+t\phi_{1}$ is a linear combination of $\phi_{0}$ and
$\phi_{1}$ (using $c_{0}=1-t$ and $c_{1}=t$ in Definition B.1). Thus, $\Gamma$
is a continuous family of linear combinations of the maps $\phi_{0}$ and
$\phi_{1}$; we show $\Gamma$ is continuous in Lemma B.2. in Appendix B.1. If
$G=[0,1]$, the linear interpolation between graphs is simply linear
interpolation between paths. For an example of linear interpolation between
graphs, see Figure 4 in Appendix B.1.

However, linear interpolation is not well-defined in
$\mathcal{G}_{\mathcal{C}}$, as we could have
$\phi_{1},\phi_{2}\in[\phi]\in\mathcal{G}_{\mathcal{C}}(G)$. In fact,
$\Gamma(t;\phi_{1},\phi_{2})=\Gamma(t;\phi_{1},\phi_{3})$ if and only if
$\phi_{1}=\phi_{2}$.

######  Definition 4.2 (Family of Interpolations).

Let $G$ be a graph and $[\phi_{0}],[\phi_{1}]\in\mathcal{G}_{\mathcal{C}}(G)$.
We define $\mathcal{C}([\phi_{0}],[\phi_{1}])$ to be the set of all linear
interpolations between elements of $[\phi_{0}]$ and of $[\phi_{1}]$.

We now demonstrate the existence of a family of interpolations between any two
equivalence classes within $(\mathcal{G}_{\mathcal{C}}(G),d_{FG})$, proving
path-connectivity.

######  Theorem 4.3 (Continuous Maps of Graphs).

For every graph $G$, the extended metric space
$(\mathcal{G}_{\mathcal{C}}(G),d_{FG})$ is path-connected. Moreover, the
connected components of $(\mathcal{G}_{\mathcal{C}},d_{FG})$ are in one-to-one
correspondence with the homeomorphism classes of graphs.

######  Proof 4.4.

Let $[\phi_{0}],[\phi_{1}]\in\mathcal{G}_{\mathcal{C}}(G)$. Let
$\Gamma\in\mathcal{C}([\phi_{0}],[\phi_{1}])$. By Lemma B.2 in Appendix B.1,
$\Gamma$ is continuous, and so $(\mathcal{G}_{\mathcal{C}}(G),d_{FG})$ is
path-connected.

Moreover, suppose $(G,[\phi_{0}]),(H,[\phi_{1}])\in\mathcal{G}_{\mathcal{C}}$
for the graphs $G,H$ which are not homeomorphic. Then,
$d_{FG}((G,[\phi_{0}]),(H,[\phi_{1}]))=\infty$, and connected components of
the extended metric space $\mathcal{G}_{\mathcal{C}}$ are vacuously in one-to-
one correspondence with homeomorphism classes of graphs.

Setting $G=[0,1]$, an identical proof holds for paths.

######  Corollary 3 (Continuous Maps of Paths).

The space $\Pi_{\mathcal{C}}$ is path-connected.

We now demonstrate the stricter property of the path-connectivity of open
distance balls:

######  Lemma 4.5 (Metric Balls in $(\mathcal{G}_{\mathcal{C}},d_{FP})$).

Metric balls with finite radius in $(\mathcal{G}_{\mathcal{C}},d_{FP})$ are
path-connected.

######  Proof 4.6.

Let $\delta\in\mathbb{R}$ such that $\delta>0$. Let
$(G,[\phi_{0}])\in\mathcal{G}_{\mathcal{C}}$.

Consider the metric ball $\mathbb{B}:=\mathbb{B}_{d_{FG}}([\phi_{0}],\delta)$
in $\mathcal{G}_{\mathcal{C}}$. Let $[\phi_{1}],[\phi_{2}]\in\mathbb{B}$. We
wish to find a path from $[\phi_{1}]$ to $[\phi_{2}]$. We first find a path in
$\mathbb{B}_{d_{FG}}([\phi_{0}],\delta)$ from $[\phi_{0}]$ to $[\phi_{2}]$, as
follows. Set

$\varepsilon=\delta-d_{FG}([\phi_{0}],[\phi_{2}]).$

By Lemma A.1, we know that there exists a homeomorphism $h_{*}:G\to G$ such
that the following inequality holds: $||\phi_{0}-\phi_{2}\circ
h_{*}||_{\infty}<d_{FG}([\phi_{0}],[\phi_{2}])+\varepsilon/2$.

Let $\Gamma\in\mathcal{C}([\phi_{0}],[\phi_{2}])$. Then, for all $t\in(0,1)$,

$\displaystyle d_{FG}(\Gamma_{t},\phi_{0})$
$\displaystyle\qquad=\inf_{h}||((1-t)\phi_{0}+t(\phi_{2}\circ
h_{*}))-\phi_{0}\circ h||_{\infty}$
$\displaystyle\qquad\leq||((1-t)\phi_{0}+t(\phi_{2}\circ h_{*}))-\phi_{0}\circ
h_{*}||_{\infty}$
$\displaystyle\qquad<d_{FG}([\phi_{0}],[\phi_{2}])+\varepsilon/2$
$\displaystyle\qquad<\delta.$

Thus, $\Gamma_{t}\in\mathbb{B}_{d_{FG}}([\phi_{1}],\delta)$, which means there
exists a path from $\phi_{0}$ to $\phi_{2}$. Similarly, we find a path
$\Gamma^{\prime}$ from $\phi_{1}$ to $\phi_{0}$. Concatentating the two paths,
$\Gamma^{\prime}\\#\Gamma$ we have a path in
$\mathbb{B}_{d_{FG}}([\phi_{0}],\delta)$ from $[\phi_{1}]$ to $[\phi_{2}]$.
Hence, metric balls with finite radius in $\mathcal{G}_{\mathcal{C}}$ are
path-connected.

Setting $G=[0,1]$, we obtain:

######  Corollary 4 (Metric Balls in $(\Pi_{\mathcal{C}},d_{FP})$).

Balls in the extended metric space $(\Pi_{\mathcal{C}},d_{FP})$ are path-
connected.

###  4.2 Immersions

An immersion is a map that is locally injectivite. Thus, self-intersections
are allowed, but a map pausing or backtracking is not. Next, we define these
notions, and give examples in Figure 2.

######  Definition 4.7 (Pausing).

We say that a path $\gamma$ _pauses_ in an interval $I\subset[0,1]$ if
$\gamma(x)=\gamma(y)$ for every $x,y\in I$. In this case,
$[\gamma]\not\in\Pi_{\mathcal{I}}$.

Another possible violation of local injectivity is _backtracking_ on a path.

######  Definition 4.8 (Backtracking).

We say that a path $\gamma$ is _backtracking_ at a point $x\in[0,1]$ if there
exists $\delta>0$ such that for every $\epsilon\in(0,\delta)$, either
$\gamma|_{(x-\epsilon,x)}\subset\gamma_{(x,x+\epsilon)}$ or
$\gamma|_{(x,x+\epsilon)}\subset\gamma|_{(x-\epsilon,x)}$.

To show the path-connectivity of spaces of immersions, the proof in Theorem
4.3 for continuous mappings is _almost_ sufficient, but these added violations
must be addressed. Thus, we introduce additional maneuvers to avoid pauses and
backtracking.

(a) Forced Backtracking

(b) Constant Map

Figure 2:  Examples of paths in $\Pi_{\mathcal{C}}$ but not
$\Pi_{\mathcal{I}}$. Figure 2(a) demonstrates a path with necessary
backtracking at the red point. Figure 2(b) demonstrates a constant path which
(vacuously) must pause. For a nontrivial example of a path with pauses,
consider any parameterization of a path sending an open interval to a point.

######  Lemma 4.9 (Rerouting Pauses).

Let $\gamma_{0},\gamma_{1}\in\widetilde{\Pi_{\mathcal{I}}}$, and let
$\Gamma:[0,1]\to\widetilde{\Pi_{\mathcal{C}}}$ be a path in
$\widetilde{\Pi_{\mathcal{C}}}$ from $\gamma_{0}$ to $\gamma_{1}$. Suppose
there exists an interval $[t_{1},t_{2}]$ such that for all
$t\in[0,1]\setminus(t_{1},t_{2})$, $\Gamma_{t}$ is an immersion. But, for all
$t\in~{}(0,1)$, $\Gamma_{t}$ has a single pause. Then, there exists a
different path $\Gamma^{*}\colon[0,1]\to\Pi_{\mathcal{I}}$ that avoids the
pause.

######  Proof 4.10.

Let $t\in[t_{1},t_{2}]$. Let the pause in $\Gamma_{t}$ be over the interval
$(a_{t},b_{t})\subset[0,1]$. Let $\varepsilon_{t}:=\min(t_{2}-t,t-t_{1})$. We
stretch the paused interval $(a_{t},b_{t})$ in $\Gamma_{t}$ by defining a map
$\Gamma^{*}_{t}:[0,1]\to\widetilde{\Pi_{\mathcal{I}}}$ as follows:

  * •

$\Gamma_{t}^{*}(-\infty,a_{t}]$ is an oriented reparameterization of
$\Gamma_{t}(-\infty,a_{t}-\varepsilon_{t}]$.

  * •

$\Gamma_{t}^{*}(a_{t},b_{t})$ is an oriented reparameterization of
$\Gamma_{t}(a_{t}-\varepsilon_{t},a_{t}]\\#\Gamma_{t}[b_{t},b_{t}+\varepsilon)$

  * •

$\Gamma_{t}^{*}[b_{t},\infty)$ is an oriented reparameterization of
$\Gamma_{t}[b_{t}+\varepsilon_{t},\infty)]$.

By construction, $\Gamma^{*}_{t}$ has removed the pause between $a_{t}$ and
$b_{t}$; hence, $\Gamma_{s}\in\widetilde{\Pi_{\mathcal{I}}}$. Putting these
maps together, we obtain a map
$\Gamma^{*}\colon[0,1]\to\widetilde{\Pi_{\mathcal{C}}}$, where

$\Gamma(t):=\begin{cases}\Gamma_{t}&\text{if }t\not\in(t_{1},t_{2})\\\
\Gamma^{*}_{t}&\text{if }t\in(t_{1},t_{2}).\end{cases}$ (2)

Moreover, $\Gamma$ is continuous in $\Pi_{\mathcal{I}}$.

Direct linear interpolation can also yield degeneracies by creating a
singleton in specific circumstances, or by creating a backtracking point. Each
are addressed in the following theorem, and a path is constructed.

######  Theorem 4.11 (Path Immersions).

The extended metric space $(\Pi_{\mathcal{I}},d_{FP})$ of paths immersed in
$\mathbb{R}^{n}$ is path-connected iff $n>1$.

######  Proof 4.12.

If $n=1$, it is easy to see that $\Pi_{\mathcal{I}}$ is not path-connected by
examining intervals with reversed orientation which trivially degenerate to a
point when constructing a path, violating local injectivity.

Now, consider $n>1$. Let $[\gamma_{0}],[\gamma_{1}]\in\Pi_{\mathcal{I}}$.
Using Definition 4.1, let $\Gamma:[0,1]\to\Pi_{\mathcal{C}}$ be the linear
interpolation from $\gamma_{0}$ to $\gamma_{1}$. This interpolation is in
$\Pi_{\mathcal{C}}$, not $\Pi_{\mathcal{I}}$, so we explain how to edit
$\Gamma$ so that it stays in $\Pi_{\mathcal{I}}$. If
$\Gamma(t)\in\widetilde{\Pi_{\mathcal{I}}}$ for each $t\in[0,1]$, we are done.
Otherwise, let $T\subset I$ be the set of times that introduce a non-immersion
(i.e., $t\in T$ iff $\Gamma(t)\not\in\widetilde{\Pi_{\mathcal{I}}}$, but
$\Gamma(t-\epsilon)\in\widetilde{\Pi_{\mathcal{I}}}$ for all $\epsilon$ small
enough). There are two things that might have happened at $t$: either an
interval collapsed to a point (a pause) or backtracking was introduced in
$\Gamma(t)$.

  1. 1.

Suppose there exists $t\in T$ where an interval pauses as in Definition 4.7
and Figure 2(b). Note that a pausing event occurs either if an interval of
$\Gamma_{t}$ becomes degenerate, or $\Gamma_{t}$ collapses to a point.

If pausing occurs only on an open interval $(a,b)\subset[0,1]$ of
$\gamma_{t}\in\Gamma_{t}$, it can be avoided using Lemma 4.9. If pausing
occurs on a closed interval $[a,b]\subset[0,1]$, we convert it to the open set
$(a-\varepsilon,b+\varepsilon)$ for small $\varepsilon$, and use Lemma 4.9. If
either $a=0$ or $b=1$, we simply redefine $\gamma_{t}$ to start at $b$ or to
end at $a$, respectively, using Lemma B.4. The pausing event is guaranteed to
conclude at some $t+\delta$ for $\delta\geq 0$ since
$[\gamma_{1}]\in\Pi_{\mathcal{I}}$, and $\Gamma$ must attain
$\gamma_{1}\in[\gamma_{1}]$.

If a pausing event stems from a full collapse to a singleton (i.e.
interpolation occurs between two colinear segments with reverse orientation,
and consequently degenerate to a point), the collapse can be circumvented by
rotating the path defining $\Gamma_{t}$, which is done in Lemma B.6.

  2. 2.

Alternatively, suppose there exists $t\in T$ which corresponds to backtracking
at a point in a path $\Gamma_{t}$ according to Definition 4.8 and Figure 2(a).
Here, $\Gamma_{t}$ can remain in $\widetilde{\Pi_{\mathcal{I}}}$ by inflating
a ball of radius $\epsilon$ for sufficiently small $\epsilon>0$ about the
backtracking point before it is created. This is included in Lemma B.8, and
shown in Figure 6(b).

For all $t\in T$, the described moves can be used to subvert lapses in local
injectivity along $\Gamma$. Hence, we construct a path $\Gamma$ by
interpolating from $\gamma_{0}$ to $\gamma_{1}$, and applying the required
move at each $t\in T$ to handle pauses or backtracking. By the arbitrariness
of $\Gamma$, we have given a class of continuous paths from any element
$\gamma_{0}\in[\gamma_{0}]$ to any $\gamma_{1}\in[\gamma_{1}]$.

######  Theorem 4.13 (Metric Balls in $(\Pi_{\mathcal{I}},d_{FP})$).

If $n>1$, then balls in the extended metric space $(\Pi_{\mathcal{I}},d_{FP})$
are path-connected.

######  Proof 4.14.

Let $[\gamma_{0}],[\gamma_{1}]\in\Pi_{\mathcal{I}}$, and let $\delta>0$. Let
$\Gamma\in\Pi_{\mathcal{I}}$ be the map $\Gamma$ in the proof of Theorem 4.11.
By Lemma 4.5, linear interpolation does not increase the Fréchet distance. By
design, avoiding singleton degeneracies by way of Lemma B.6 also does not
increase the Fréchet distance. Moreover, by construction, the map $\Gamma^{*}$
of Lemma 4.9 preserves the Fréchet distance. The maneuver in Lemma B.8 could
potentially increase $d_{FP}(\Gamma_{t},\gamma_{1})$ at some time $t\in[0,1]$,
but in this case any critical backtracking points can be perturbed slightly in
order to no longer define the $d_{FP}(\Gamma_{t},\gamma_{1})$. Hence, these
moves need not result in $d_{FP}(\Gamma_{t},\gamma_{1})>\delta$, meaning that
$\Gamma_{t}\in\mathbb{B}_{d_{FP}}(\phi_{1},\delta)$, and balls in
$\Pi_{\mathcal{I}}$ are path-connected.

We use the same maneuvers from Theorem 4.11 in the context for graphs under
$d_{FG}$.

######  Theorem 4.15 (Graph Immersions).

For every graph $G$, the extended metric space
$(\mathcal{G}_{\mathcal{I}}(G),d_{FG})$ is path-connected. Connected
components of the extended metric space $(\mathcal{G}_{\mathcal{I}},d_{FG})$
are in one-to-one correspondence with the homeomorphism classes of graphs.

######  Proof 4.16.

We construct $\Gamma$ identically to Theorem 4.11, but interpolation occurs
among each edge of $G$ in $\mathcal{G}_{\mathcal{I}}(G)$ rather than between
individual segments. As in Theorem 4.11, local injectivity can only be
violated by pauses and backtracking on edges, which are handled using Lemma
4.9, Lemma B.6, and Lemma B.8 on each edge. If
$(G,[\phi_{0}]),(H,[\phi_{1}])\in\mathcal{G}_{\mathcal{I}}$ for $G,H$ which
are not homeomorphic, then $d_{FG}((G,[\phi_{0}]),(H,[\phi_{1}]))=\infty$.

Similarly, we can adopt Theorem 4.13 for each edge in a graph to show path-
connectivity of balls in $\mathcal{G}_{\mathcal{I}}$.

######  Theorem 4.17 (Metric Balls in
$(\mathcal{G}_{\mathcal{I}}(G),d_{FG})$).

For every graph $G$, the balls in the extended metric space
$(\mathcal{G}_{\mathcal{I}}(G),d_{FG})$ are path-connected.

######  Proof 4.18.

Let $[\phi]\in\mathcal{G}_{\mathcal{I}}$, and let $\delta>0$. Let $\mathbb{B}$
be the intersection
$\mathbb{B}_{d_{FG}}(\phi,\delta)\cap\mathcal{G}_{\mathcal{I}}(G)$. Let
$[\phi_{0}],[\phi_{1}]\in\mathbb{B}$. Construct the path
$\Gamma:[0,1]\to\mathbb{B}$ from $[\phi_{0}]$ to $[\phi_{1}]$ in the same way
as Theorem 4.15. Just as in Theorem 4.13, linear interpolation and the moves
in Lemma B.6, Lemma B.8, and Lemma 4.9 mandate that $\Gamma(t)\in\mathbb{B}$
for every $t\in(0,1)$ identically to the path Fréchet distance.

###  4.3 Embeddings

Lastly, we examine the path-connectedness property of the analogous spaces of
embeddings.

######  Theorem 4.19 (Path Embeddings).

The extended metric space $(\Pi_{\mathcal{E}},d_{FP})$ is path-connected in
$\mathbb{R}^{n}$ if and only if $n>1$.

######  Proof 4.20.

If $n=1$, two paths with reverse orientations are not path-connected.

Now, let $n>1$, and let $[\gamma_{0}],[\gamma_{1}]\in\Pi_{\mathcal{E}}$. By
Alexander’s trick,333Two embeddings of the $n$-ball are isotopic, first proven
by Alexander [3]; see also [15, §4]. there exists $s_{0}\in[0,1]$ such that
$\gamma_{0}^{\prime}:=\gamma_{0}|_{[s,1]}$ and $s_{1}\in[0,1]$ such that
$\gamma_{1}^{\prime}:=\gamma_{1}|_{[s_{1},1]}$, where $s_{0}$ and $s_{1}$ are
nearly straight. Let $\angle$ be the angle between the segments
$\gamma_{0}^{\prime}$ and $\gamma_{1}^{\prime}$. Let
$S\colon[\frac{1}{4},\frac{2}{4}]\to\Pi_{\mathcal{E}}$ be the map rotating
$\gamma_{0}^{\prime}$ by $\angle$ to become parallel with
$\gamma_{1}^{\prime}$. Finally, let $\Gamma$ be the interpolation from
$\gamma_{0}^{\prime}\circ S$ to $\gamma_{1}^{\prime}$.

Define $P\colon[0,1]\to\Pi_{\mathcal{E}}$ as the resulting composition:

$P(t)=\begin{cases}\gamma_{0}~{}|_{[(1-t)s,1]},&t\in[0,\frac{1}{4}]\\\
S(t),&t\in[\frac{1}{4},\frac{2}{4}]\\\
\Gamma(t)&t\in[\frac{2}{4},\frac{3}{4}]\\\
\gamma_{1}~{}|_{[(1-t)s,1]},&t\in[\frac{3}{4},1].\end{cases}$

The steps attaining $\gamma_{0}^{\prime}$ and $\gamma_{1}^{\prime}$, as
nothing else than a restriction of $\gamma_{0}$ and $\gamma_{1}$, are
continuous. Moreover, $S$ is continuous as the rotation of
$\gamma_{0}^{\prime}$, and $\Gamma$ is continuous by Lemma B.2. By the
arbitrariness of the constructed path and $\gamma_{0},\gamma_{1}$, there is a
family of continuous paths for any
$\gamma_{0}\in[\gamma_{0}],\gamma_{1}\in[\gamma_{1}]$, and $\Pi_{\mathcal{E}}$
is path-connected.

Figure 3: Two embedded paths $\gamma_{0},\gamma_{1}$ in $\mathbb{R}^{2}$ and
$\mathbb{R}^{3}$ respectively, for which constructing a path
$\Gamma:[0,1]\to\Pi_{\mathcal{E}},\Gamma(0)=\gamma_{0},\Gamma(1)=\gamma_{1}$
is not possible without having
$\Gamma(t)\not\in\mathbb{B}_{d_{FP}}(\gamma_{1},d_{FP}(\gamma_{0},\gamma_{1}))$
for some $t\in[0,1]$.

Moreover, in high dimensions we can construct a path in $\Pi_{\mathcal{E}}$
not increasing the Fréchet distance.

######  Theorem 4.21 (Metric Balls in $(\Pi_{\mathcal{E}},d_{FP})$).

If $n\geq 4$, then balls with finite radius in the extended metric space
$(\Pi_{\mathcal{E}},d_{FP})$ are path-connected in $\mathbb{R}^{n}$.

######  Proof 4.22.

If $n\geq 4$, the same map $\Gamma$ given in Theorem 4.11 is sufficient,
except that self-crossings must be avoided. At each $s\in[0,1]$ where a self-
crossing would occur, we perturb $\Gamma$ by a sufficiently small amount in
order to avoid a self-crossing without increasing the Fréchet distance using
the maneuver in Lemma B.12.

A simple examination shows that metric balls are not path-connected in low
dimensions.

######  Theorem 4.23 (Metric Balls in $(\Pi_{\mathcal{E}},d_{FP})$).

If $n\in\\{1,2,3\\}$, then balls with finite radius in the extended metric
space $(\Pi_{\mathcal{E}},d_{FP})$ are not path-connected in $\mathbb{R}^{n}$.

######  Proof 4.24.

For $n=1$, let $[\gamma]\in\Pi_{\mathcal{E}}$. Let $\gamma^{-1}:=\gamma(1-t)$,
and note that $\gamma^{-1}\in\Pi_{\mathcal{E}}$. If $n=2$, consider two paths
within a fixed Fréchet ball that are much wider than their Fréchet distance.
If $n=3$, consider two paths with small Fréchet distance that form a loop,
with one section passing under the other. If these loops have reversed
orientation between the two paths, the Fréchet distance must increase. See
Figure 3 for examples.

In the setting for graphs, the path-connectedness property reduces to a knot
theory problem if $n\leq 3$, and is not maintained. For $n\geq 4$, we use the
existence of a sequence of Reidemeister moves [25] from any tame knot to
another to construct paths in $\mathcal{G}_{\mathcal{E}}$.

######  Theorem 4.25 (Path-Connectivity of
$(\mathcal{G}_{\mathcal{E}},d_{FG})$, $n\geq 4$).

For all graphs $G$ and $n\geq 4$, the extended metric space
$(\mathcal{G}_{\mathcal{E}}(G),d_{FG})$ is path-connected. Moreover, connected
components of the extended metric space $(\mathcal{G}_{\mathcal{E}},d_{FG})$
are in one-to-one correspondence with homeomorphism classes of graphs.

######  Proof 4.26.

Let $G$ be a graph, and $\phi_{0},\phi_{1}\in\mathcal{G}_{\mathcal{E}}(G)$. If
$n\geq 4$, any tame knot can be unwound by a sequence of Reidemeister moves
into the unknot. Construct $\Gamma:[0,1]\to\mathcal{G}_{\mathcal{E}}(G)$ by
linear interpolating until some $t\in(0,1)$ causes $\Gamma_{t}$ to self-
intersect. At $t$, there exists a Reidemeister move allowing the crossing
event to occur. Hence, any sequence of knots and free edges comprising
$\phi_{0}$ and $\phi_{1}$ can be unwound to a sequence of unknots and straight
edges, and then interpolated accordingly. Consequently, there exists a path
from $\phi_{0}$ to $\phi_{1}$ in $(\mathcal{G}_{\mathcal{E}}(G),d_{FG})$. Note
that we require $\phi_{0},\phi_{1}$ are rectifiable in Section 2.

In dimension $4$ or higher, the path-connectivity of balls in
$\mathcal{G}_{\mathcal{E}}(G)$ is shown in the same way as for paths.

######  Theorem 4.27 (Metric Balls in
$(\mathcal{G}_{\mathcal{E}}(G),d_{FG})$).

For all graphs $G$ and $n\geq 4$, metric balls in the space
$(\mathcal{G}_{\mathcal{E}}(G),d_{FG})$ are path-connected.

######  Proof 4.28.

The proof is identical to that in Lemma B.12, but Reidemeister moves are used
for each edge in a graph rather than a single segment.

##  5 Conclusion

In this paper, we studied some fundamental topological properties of spaces of
paths and graphs in Euclidean space under the Fréchet distance. In particular,
we investigated metric properties of the Fréchet distance on paths and graphs,
as well as studying the path-connectedness of metric balls in the space of
such graphs. While this work is theoretical and mathematical in nature, we
feel that establishing the underlying properties of the topological spaces it
can define provides an important theoretical backdrop, which is especially
critical due to the widespread popularity of the Fréchet distance in
computational geometry, and the growing popularity of its extension for
graphs. Our contribution begins a careful study of the Fréchet distance and
its topological properties. Extensions to this work abound, and include
examining core topological properties of other distance measures in
computational geometry, as well as other important properties of the Fréchet
distance.

## Acknowledgements

We thank our coauthors from [9] for the initial conversations that inspired
this paper. In addition, the authors thank the National Science Foundation;
specifically, Erin Chambers is partially supported by NSF awards 2106672 and
1907612, Brittany Terese Fasy and Benjamin Holmgren are partially supported by
award 1664858, Fasy is also supported by award 2046730, and Carola Wenk is
partially supported by award 2107434.

## References

  * [1] P. K. Agarwal, R. B. Avraham, H. Kaplan, and M. Sharir.  Computing the discrete Fréchet distance in subquadratic time.  SIAM Journal on Computing, 43(2):429–449, 2014.
  * [2] M. Ahmed and C. Wenk.  Constructing street networks from gps trajectories.  In Algorithms – ESA 2012, pages 60–71, Berlin, Heidelberg, 2012\. Springer Berlin Heidelberg.
  * [3] J. W. Alexander.  On the deformation of an $n$ cell.  Proceedings of the National Academy of Sciences, 9(12):406–407, 1923.
  * [4] H. Alt and M. Godau.  Computing the Fréchet distance between two polygonal curves.  IJCGA, 5(1–2):75–91, 1995.
  * [5] H. Alt, C. Knauer, and C. Wenk.  Matching polygonal curves with respect to the Fréchet distance.  In A. Ferreira and H. Reichel, editors, STACS 2001, pages 63–74, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
  * [6] B. Aronov, S. Har-Peled, C. Knauer, Y. Wang, and C. Wenk.  Fréchet distance for curves, revisited.  In Y. Azar and T. Erlebach, editors, Algorithms – ESA 2006, pages 52–63, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [7] K. Buchin, M. Buchin, and A. Schulz.  Fréchet distance of surfaces: Some simple hard cases.  In European Symposium on Algorithms, pages 63–74. Springer, 2010\.
  * [8] K. Buchin, T. Ophelders, and B. Speckmann.  Computing the Fréchet distance between real-valued surfaces.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2443–2455. ACM, 2017.
  * [9] M. Buchin, E. Chambers, P. Fang, B. T. Fasy, E. Gasparovic, E. Munch, and C. Wenk.  Distances between immersed graphs: Metric properties.  La Matematica, 2(1):197–222, 2023.
  * [10] M. Buchin, A. Krivosija, and A. Neuhaus.  Computing the Fréchet distance of trees and graphs of bounded tree width.  In Proceedings of the 36th European Workshop on Computational Geometry, 2020.
  * [11] E. Chambers, B. T. Fasy, Y. Wang, and C. Wenk.  Map-matching using shortest paths.  In ACM Transactions on Spatial Algorithms and Systems, pages 1–17. Association for Computing Machinery, 2020.
  * [12] E. W. Chambers, E. Colin de Verdière, J. Erickson, S. Lazard, F. Lazarus, and S. Thite.  Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time.  Computational Geometry, 43(3):295–311, 2010.  Special Issue on 24th Annual Symposium on Computational Geometry (SoCG’08).
  * [13] D. Chen, A. Driemel, L. J. Guibas, A. Nguyen, and C. Wenk.  Approximate map matching with respect to the fr´echet distance.  pages 75–83, 2011.
  * [14] C. Colombe and K. Fox.  Approximating the (continuous) Fréchet distance.  In K. Buchin and E. Colin de Verdiére, editors, 37th International Symposium on Computational Geometry (SoCG, 2021), 2021.
  * [15] E. Denne and J. M. Sullivan.  Convergence and isotopy type for graphs of finite total curvature.  Discrete differential geometry, pages 163–174, 2008.
  * [16] A. Driemel and S. Har-Peled.  Jaywalking your dog: Computing the Fréchet distance with shortcuts.  SIAM Journal on Computing, 42(5):1830–1866, 2013.
  * [17] A. Driemel, S. Har-Peled, and C. Wenk.  Approximating the Fréchet distance for realistic curves in near linear time.  Discrete and Computational Geometry, 48(1):94–127, Feb. 2012.
  * [18] A. Driemel, I. van der Hoog, and E. Rotenburg.  On the discrete fréchet distance in a graph.  In M. Kerber and X. Goaoc, editors, Proceedings of the Symposium on Computational Geometry, 2022.
  * [19] H. Edelsbrunner and J. L. Harer.  Computational Topology: An Introduction.  American Mathematical Society, 2010.
  * [20] P. Fang and C. Wenk.  The Fréchet distance for plane graphs.  In Proceedings of the 37th European Workshop on Computational Geometry, 2021.
  * [21] M. Fréchet.  Sur quelques points du calcul fonctionnel.  Rendiconti del Circolo Mathematico di Palermo, 22:1–74, 1906.  Paragraphs 78–80.
  * [22] A. F. C. IV and C. Wenk.  Geodesic Fréchet distance inside a simple polygon.  ACM Trans. Algorithms, 7(1), dec 2010.
  * [23] L. Jiří.  Basic Analysis: Introduction to Real Analysis, volume 5.6.  2022\.
  * [24] M. Musleh, S. Abbar, R. Stanojevic, and M. Mokbel.  Qarta: an ml-based system for accurate map services.  Proceedings of the VLDB Endowment, 14(11):2273––2282, July 2021\.
  * [25] K. Reidemeister.  Knoten und gruppen.  In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 5, pages 7–23. Springer, 1927.

##  Appendix A Distances and Topology

Let $\bar{\mathbb{R}}$ denote the extended real line:
$\bar{\mathbb{R}}=\mathbb{R}\cup\pm\infty$. We now provide the basic
definitions relating to distances and topology used throughout this paper.

###  A.1 Graphs

Graphs are a central object studied in this paper.

Throughout this paper, we use the term _graph_ to mean a _multi-graph_. A
multi-graph $G=(V,E)$ is a finite set of vertices $V$ and edges $E$. Self-
loops and multiple edges between two vertices are allowed in this setting. A
graph is an example of a more general structure called a CW complex, which we
topologize as follows: (1) the topology on $G$ restricted to $V$ is the
discrete topology; (2) for a edge $e$, the open sets restricted to is closure
$\bar{e}$ are those induced by the subspace topology on
$[0,1]\subset\mathbb{R}$ and a homeomorphism $[0,1]\to\bar{e}$; (3) we take
the quotient topology on $\left(\cup_{v\in V}\right)\cup\left(\cup_{e\in
E}\bar{e}\right)$.

###  A.2 Fréchet Distance

We defined the path and graph Fréchet distances in Section 2. The path Fréchet
distance is well-studied [21, 20, 7, 8, 10, 4, 6, 1, 17, 5, 16, 22, 12, 18,
11, 14, 13]. The graph Fréchet distance has been less studied, but many
results for paths transfer to graphs.

The proof of the following lemma follows from the definition of Fréchet
distance and the definition of infimum.

######  Lemma A.1 (Approximator).

For all graphs $G$, if $[\phi_{0}],[\phi_{1}]\in\Pi_{\mathcal{C}}(G)$, then
for every $\varepsilon>0$, there exists a homeomorphism $h_{*}\colon G\to G$
such that

$||\phi_{0}-\phi_{1}\circ h||_{\infty}<d_{FG}(\phi_{0},\phi_{1})+\epsilon.$

######  Proof A.2.

By Definition 2,

$d_{FG}([\phi_{1}],[\phi_{2}])=\inf_{h}||\phi_{1}-\phi_{2}\circ h||_{\infty}.$

Then, by the definition of infimum, for every $\varepsilon>0$, there exists
$h_{*}:G\to G$ such that

$\displaystyle||\phi_{1}-\phi_{2}\circ h_{*}||_{\infty}$
$\displaystyle<\inf_{h}||\phi_{1}-\phi_{2}\circ h||_{\infty}+\varepsilon/2$
$\displaystyle=d_{FG}([\phi_{1}],[\phi_{2}])+\varepsilon/2,$

as was to be shown.

###  A.3 Defining Spaces from Distances and Metrics

Given a set $\mathbb{X}$ and a
$d\colon\mathbb{X}\times\mathbb{X}\to\bar{\mathbb{R}}_{\geq 0}$, we topologize
$\mathbb{X}$ as follows:

######  Definition A.3 (The Open Ball Topology).

Let $\mathbb{X}$ be a set and
$d\colon\mathbb{X}\times\mathbb{X}\to\bar{\mathbb{R}}_{\geq 0}$ a distance
function. For each $r>0$ and $x\in\mathbb{X}$, let
$\mathbb{B}_{d}(x,r):=\\{y\in\mathbb{X}~{}|~{}d(x,y)<r\\}$. The open ball
topology on $\mathbb{X}$ with respect to $d$ is the topology generated by
$\\{\mathbb{B}_{d}(x,r)~{}|~{}x\in\mathbb{X},r>0\\}$. We call $(\mathbb{X},d)$
a _distance space_.

In words, $\mathbb{B}_{d}(x,r)$ denotes the open ball of radius $r$ centered
at $x$ with respect to $d$. We use these open balls to generate a topology on
$\mathbb{X}$, allowing $x$ to range over $\mathbb{X}$ and $r$ to range over
all positive real numbers.

We are particularly interested in distance functions that are either a pseudo-
metric or a metric. These are defined as follows.

######  Definition A.4 (Pseudo-Metric).

Let $\mathbb{X}$ be a set and let
$d\colon\mathbb{X}\times\mathbb{X}\to\bar{\mathbb{R}}_{\geq 0}$ be a distance
function. We call $d$ a _pseudo-metric_ on $\mathbb{X}$ if $d$ satisfies the
following:

  * •

Finiteness: $d(x,y)<\infty$ for all $x,y\in\mathbb{X}$.

  * •

Identity: $d(x,x)=0$ for all $x\in\mathbb{X}$.

  * •

Symmetry: $d(x,y)=d(y,x)$ for all $x,y\in\mathbb{X}$.

  * •

Subadditivity (the triangle inequality): $d(x,z)\leq d(x,y)+d(y,z)$ for all
$x,y,z\in\mathbb{X}$

If $d$ satisfies everything except finiteness, then we call $d$ an _extended
pseudo-metric_.

In order to be a metric, $d$ must fulfill stricter criteria:

######  Definition A.5 (Metric).

Let $\mathbb{X}$ be a set and let the function
$d\colon\mathbb{X}\times\mathbb{X}\to\bar{\mathbb{R}}_{\geq 0}$ be a pseudo-
metric. We say that $d$ is a _metric_ if $d$ also satisfies:

  * •

Seperability: for any $x,y\in\mathbb{X}$, if $x\not=y$, then $d(x,y)>0$.

Often, if $(\mathbb{X},d)$ is a pseudo-metric space, a standard procedure is
to define an equivalence class for $x,y\in\mathbb{X}$ where $x\sim y$ if
$d(x,y)=0$. Then, the quotient space
${\raisebox{1.99997pt}{$\mathbb{X}$}\left/\raisebox{-1.99997pt}{$\sim$}\right.}$
is a metric space.

Common examples of metrics on function spaces are those induced by
$L_{p}$-norms. For example, let $(\mathbb{Y},d_{\mathbb{Y}})$ be distance
space, let $\mathbb{X}$ be any topological space, and let
$f,g\colon\mathbb{X}\to\mathbb{Y}$. Then, the distance induced by the
$L_{\infty}$-norm between $f$ and $g$ is:

$||f-g||_{\infty}=\max_{x\in\mathbb{X}}d_{\mathbb{Y}}(f(x),f(y)).$

###  A.4 Paths and Maps

With the basic definitions from topology in hand, we are equipped to define a
property of fundamental interest in topology: path-connectedness.

######  Definition A.6 (Path).

A _path_ in a topological space $\mathbb{X}$ between two elements
$a,b\in\mathbb{X}$, is defined to be a continuous map
$\gamma:[0,1]\to\mathbb{X}$ where $\gamma(0)=a$, and $\gamma(1)=b$.

Given two paths $\gamma_{1},\gamma_{2}\colon[0,1]\to\mathbb{X}$ such that
$\gamma_{1}(1)=\gamma_{2}(0)$, we combine them by taking both at double-speed.
This is called the concatenation of paths. In particular,
$\gamma_{1}\\#\gamma_{2}\colon[0,1]\to\mathbb{R}^{n}$ is defined by:

$\gamma_{1}\\#\gamma_{2}(t):=\begin{cases}\gamma_{1}(2t)&t\in[0,0.5].\\\
\gamma_{2}(2t-1)&\text{otherwise}.\end{cases}$

Given one path $\gamma\colon[0,1]\to\mathbb{X}$ and an interval
$[a,b]\subseteq[0,1]$, the restriction of $\gamma$ to $[a,b]$ is also a path,
given by:

$\gamma|_{[a,b]}(t):=\gamma(a+t(b-a)).$

With the definition of paths, we define a primary property of interest in this
paper: path-connectivity.

######  Definition A.7 (Path-Connectivity).

A topological space $\mathbb{X}$ is called _path-connected_ if there exists a
_path_ between any two elements in $\mathbb{X}$.

We also define the path-connectedness property specifically for distance
balls:

######  Definition A.8 (Path-Connectivity of Balls).

Let $(\mathbb{X},d)$ be a topological space, let $x\in\mathbb{X}$. We say that
the distance balls in $(\mathbb{X},d)$ are _path-connected_ if for every
$x\in\mathbb{X}$ and $r\in\mathbb{R}_{\geq 0}$, the distance ball
$\mathbb{B}_{d}(y,r)$ is path-connected.

And, the _length_ of a path in a distance space is given by:

######  Definition A.9 (Length).

Let $(\mathbb{X},d)$ be a distance space and let $\gamma$ be a _path_ in
$(\mathbb{X},d)$. Let $\mathcal{P}$ be the set of all finite subsets
$P=\\{t_{i}\\}$ of $[0,1]$ such that such that $0=t_{0}<t_{1}<\ldots<t_{n}=1$.
The _length_ $L_{d}(\gamma)$ of $\gamma$ is:

$L_{d}(\gamma):=\sup_{P\in\mathcal{P}}\sum_{i=1}^{n}{d(\gamma(t_{i}),\gamma(x_{i-1}))}.$

Additionally, it is often useful in our setting to reparameterize paths, both
to define the Fréchet distance and to maintain properties such as injectivity
in a map.

######  Definition A.10 (Reparameterization).

Let $\mathbb{X},\mathbb{Y}$ be a topological spaces,
$\phi\colon\mathbb{X}\to\mathbb{Y}$, and $h\colon\mathbb{X}\to\mathbb{X}$ is a
homeomorphism. Then, we call $\phi\circ h$ a reparameterization of $\phi$. In
the setting where $\mathbb{X}=[0,1]$ and $h(0)=0$, we call $\phi\circ h$ an
_orientation-preserving_ reparameterization.

##  Appendix B Omitted Details for Path-Connectivity

In this appendix, we provide additional context for the proofs of path-
connectivity in Section 4.

###  B.1 Additional Details on Interpolation

Given two continuous maps of the same graph into $\mathbb{R}^{n}$, we define
the interpolation between them. First, we need to define linear combinations
of graphs (and paths).

######  Definition B.1 (Linear Combination of Graphs).

Let $G$ be a graph, let $\phi_{1},\phi_{2}:[0,1]\to\mathbb{R}^{n}$ be
continuous, rectifiable maps, and $c_{1},c_{2}\in\mathbb{R}$. Then, the linear
combination $\phi=c_{1}\phi_{1}+c_{2}\phi_{2}$ is defined as follows: the map
$\phi\colon G\to\mathbb{R}^{n}$ is defined by
$\phi(x):=c_{2}\phi_{1}(x)+c_{2}\phi_{2}(x)$. In this case, we may also say
$(G,\phi)$ is a linear combination of graph-map pairs $(G,\phi_{1})$ and
$(G,\phi_{2})$.

In this definition, we observe that $\phi$ is continuous (since $\phi_{0}$ and
$\phi_{1}$ are continuous), which means that linear combinations are well-
defined in the set of all continuous, rectifiable maps. It is not well defined
in the space $\mathcal{G}_{\mathcal{C}}(G)$ overall.

######  Lemma B.2 (Linear Interpolation is Continuous).

For all graphs $G$, linear interpolation between graphs in
$\mathcal{G}_{\mathcal{C}}(G)$ (and hence between homeomorphic graphs in
$\mathcal{G}_{\mathcal{C}}$) is a continuous function.

######  Proof B.3.

Let $[\phi_{0}],[\phi_{1}]\in\mathcal{G}_{\mathcal{C}}(G)$. Let
$\Gamma\colon[0,1]\to\mathcal{G}_{\mathcal{C}}(G)$ be the linear interpolation
from $\phi_{0}$ to $\phi_{1}$.

We prove that $\Gamma$ satisfies the $\varepsilon$-$\delta$ definition of
continuity. Let $\varepsilon>0$. Set
$\delta=\frac{\varepsilon}{d_{FG}([\phi_{0}],[\phi_{1}])}$. Let $s,t\in[0,1]$
such that $|s-t|<\delta$. Then, we have

$\displaystyle d_{FG}\left([\Gamma_{t}],[\Gamma_{s}]\right)$
$\displaystyle~{}=d_{FG}([(1-t)\phi_{0}+t\phi_{1}],[(1-s)\phi_{0}+s\phi_{1}])$
$\displaystyle~{}=\inf_{h}~{}||((1-t)\phi_{0}+t\phi_{1})-((1-s)\phi_{0}+s\phi_{1})\circ
h||_{\infty},$

where $h$ ranges over all reparameterizations of $[0,1]$. Continuing, we find:

$\displaystyle d_{FG}\left([\Gamma_{t}],[\Gamma_{s}]\right)$
$\displaystyle~{}=\inf_{h}~{}||(s-t)\phi_{0}+(t-s)\phi_{1}\circ h||_{\infty}$
$\displaystyle~{}=|t-s|\inf_{h}~{}||-\phi_{0}+\phi_{1}\circ h||_{\infty}$
$\displaystyle~{}<\delta\cdot\inf_{h}~{}||-\phi_{0}+\phi_{1}\circ
h||_{\infty}$ $\displaystyle~{}=\varepsilon,$

by definition of $\delta$.

And so, we have shown that $\Gamma$ satisfies the the $\varepsilon$-$\delta$
definition of continuity. In extended metric spaces, the
$\varepsilon$-$\delta$ definition of continuity is equivalent to topological
continuity (e.g., see proof in [23, Lemma 7.5.7] for metric spaces). Thus, we
conclude that linear interpolation between graphs in
$\mathcal{G}_{\mathcal{C}}{G}$ is continuous.

Setting $G=[0,1]$, an identical argument shows that linear interpolation
between paths in $\Pi_{\mathcal{C}}$ is also continuous.

######  Corollary 5 (Linear Interpolation between Paths).

For all $[\gamma_{0}],[\gamma_{1}]\in\Pi_{\mathcal{C}}$, the linear
interpolation from $\gamma_{0}$ to $\gamma_{1}$ is continuous.

Figure 4:  The interpolation between two embeddings of a graph in
$\mathbb{R}^{n}$. For simplicity, we show the interpolation between the
vertices in the embeddings, and the interpolation between edges is inferred
accordingly.

###  B.2 Paths Between Immersions in Greater Detail

This subsection includes additional details to maintain local injectivity for
an arbitrary path $\Gamma:[0,1]\to\Pi_{\mathcal{I}}$. We begin by examining
the case where pausing occurs on the closed interval $[a,b]\subset[0,1]$ in
the domain of an immersed path $\gamma_{t}\in\Gamma_{t}$, and the interval
includes either $0$ or $1$. We subvert this by finding an alternate (but
‘close’) path $\Gamma^{*}$.

######  Lemma B.4 (Pausing at Endpoints).

Let $[\gamma_{0}],[\gamma_{1}]\in\Pi_{\mathcal{I}}$, and let
$\Gamma:[0,1]\to\Pi_{\mathcal{C}}$ be a path in $\Pi_{\mathcal{C}}$ starting
at $\gamma_{0}$ and ending at $\gamma_{1}$. Suppose that there exists an
interval $[t_{1},t_{2}]\subset[0,1]$ such that for
$t\in[0,1]\setminus(t_{1},t_{2})$, $\Gamma_{t}$ is an immersion and, for
$t\in(0,1)$, $\Gamma_{t}$ has a single pause (and no other violations of local
injectivity). Then, there exists an alternate path $\Gamma^{*}$ in
$\Pi_{\mathcal{C}}$ starting at $\gamma_{0}$ and ending at $\gamma_{1}$ such
that $\Gamma^{*}$ is a path in $\Pi_{\mathcal{I}}$.

######  Proof B.5.

We use the same idea as in Lemma 4.9, but instead stretch the unit interval
into only one side of the original domain of the path $\Gamma_{t}$. That is:

$\Gamma_{t}^{*}(x):=\begin{cases}\Gamma_{t}(x\cdot a)&\text{if }b=1\\\
\Gamma_{t}((x-b)\cdot(1-b)+b)&\text{if }a=0\end{cases}$ (3)

If $\Gamma_{t}$ pauses on $[a,1]$, we know that the we can focus on the image
of $[0,a]$. Likewise, if $\Gamma_{t}$ pauses on $[0,b]$, we turn to the image
of $[b,1]$. Then, replace $\Gamma_{t}$ that pauses with the newly defined
$\Gamma^{*}_{t}$. And so, we define a new map
$\Gamma^{*}\colon[0,1]\to\Pi_{\mathcal{C}}$ as follows:

$\Gamma^{*}(t):=\begin{cases}\Gamma_{t}&\text{if
}t\not\in(t-\varepsilon,t+\delta)\\\ \Gamma^{*}_{t}&\text{if
}t\in(t-\varepsilon,t+\delta)\end{cases}$ (4)

Indeed, it is easy to verify that each $\Gamma_{t}^{*}$ preserves local
injectivity so $\Gamma_{t}^{*}\in\Pi_{\mathcal{I}}$. Moreover, $\Gamma^{*}$ is
continuous.

We now examine the case when linear interpolation results in a singleton,
which causes a degeneracy in spaces of immersions. We give a maneuver to
subvert this for paths.

######  Lemma B.6 (Dodging Singletons).

Let $[\gamma_{0}],[\gamma_{1}]\in\Pi_{\mathcal{I}}$, and let
$\Gamma:[0,1]\to\Pi_{\mathcal{C}}$ be a linear interpolation from $\gamma_{0}$
to $\gamma_{1}$. Let $t\in[0,1]$ such that $\Gamma(t)$ is a constant map,
forcing $\Gamma(t)\not\in\Pi_{\mathcal{I}}$. We can avoid this total
degeneracy by rotating $\Gamma(t)$.

######  Proof B.7.

Linear interpolation of $\gamma_{0}$ to $\gamma_{1}$ produces a singleton if
the two equivalence classes of paths are colinear with reversed orientation.
Hence, if $\Gamma_{t}$ degenerates to a constant map, there exists
sufficiently small $\epsilon>0$ to continuously rotate $\Gamma(t-\epsilon)$ by
$\pi$ without forcing
$d_{FP}(\Gamma(t),\gamma_{1})>d_{FP}(\gamma_{0},\gamma_{1})$. Thereby
reversing the orientation of $\Gamma(t+\epsilon)$, and avoiding the constant
map for any $\gamma_{t}\in\Gamma_{t}$. See Figure 5 for an example.

(a) Paths with reversed orientation

(b) Interpolate

(c) Rotate when sufficiently close

Figure 5:  For colinear paths with opposing orientation, rotating by $\pi$
avoids degenerating to the constant map, keeping $\Gamma$ in
$\Pi_{\mathcal{I}}$. Moreover, rotation with sufficiently small Fréchet
distance maintains the path-connectivity of balls.

We now consider the case of backtracking during linear interpolation, which
violates local injectivity. We introduce a maneuver to solve this potential
degeneracy in spaces of immersions.

######  Lemma B.8 (The Q-Tip Maneuver).

Let $[\gamma_{0}],[\gamma_{1}]\in\Pi_{\mathcal{I}}$, and let
$\Gamma:[0,1]\to\Pi_{\mathcal{C}}$ be a linear interpolation from $\gamma_{0}$
to $\gamma_{1}$. Let $t\in[0,1]$ such that $\Gamma(t)$ creates backtracking
for some $\Gamma(t)$. Inflating a ball about the critical backtracking point
corrects this violation of injectivity.

######  Proof B.9.

In the scenario of a backtracking event, local injectivity is only violated at
the exact critical point $\Gamma_{t}(x)$ for $x\in[0,1]$ where backtracking
occurs. For sufficiently small $\varepsilon,\delta>0$, continuously inflate a
ball of radius $\delta$ about $\Gamma_{t-\varepsilon}(x)$ such that
$d_{FP}([\Gamma{t-\epsilon}],[\gamma_{1}])$ remains fixed, creating the path
$\Gamma^{*}_{t}$ with a ball replacing the critical point, so that
$\Gamma^{*}_{t}\in\widetilde{\Pi_{\mathcal{I}}}$. Then, replace any
backtracking $\Gamma_{t}$ with the corresponding $\Gamma^{*}_{t}$. For every
$t\in[0,1]$ it holds that $\Gamma_{t}\in\Pi_{\mathcal{I}}$, and by the
continuity of the inflation, $\Gamma$ remains continuous. For an example of
this maneuver, see Figure 6(b).

(a) Example path with backtracking

(b) Inflate the critical backtracking point

Figure 6:  Reconcile forced backtracking along a path by inflating a ball
about the critical backtracking point, thereby maintaining local injectivity.

###  B.3 Balls of Path Embeddings in Greater Detail

In what follows, we elaborate on counterexamples for the path-connectivity of
balls in $\Pi_{\mathcal{E}}$ and $\mathcal{G}_{\mathcal{E}}$. We begin with a
counterexample for path embeddings in $\mathbb{R}^{2}$.

We continue with a brief description of counterexamples for the path-
connectivity of embedded paths in $\mathbb{R}^{3}$.

######  Lemma B.10 (3d Balls in $\Pi_{\mathcal{E}}$).

If $n=3$, metric balls in the space $(\Pi_{\mathcal{E}},d_{FP})$ of embedded
paths in $\mathbb{R}^{n}$ are not path-connected.

######  Proof B.11.

Metric balls are not in general path-connected in three dimensions. For a
simple counterexample, suppose $\gamma_{0}$ comprises a loop in
$\mathbb{R}^{3}$, where a segment crossed on top of itself, avoiding self-
intersection by some small distance $\delta$, with long tails at either end of
the crossing of length $2\delta$. Suppose also that $\gamma_{1}$ comprises the
mirror image of $\gamma_{0}$. Then, $d_{FP}=\delta$, but it is not possible to
construct a path from $\gamma_{0}$ to $\gamma_{1}$ without increasing the
Fréchet distance between the two, since $\gamma_{0}$ must conduct a self-
crossing, which increases the Fréchet distance by at least $2\delta$. Again,
see Figure 3

We conclude with additional details demonstrating the path-connectivity of
balls for embedded paths in $\mathbb{R}^{4}$ or higher.

######  Lemma B.12 (Balls in $(\Pi_{\mathcal{E}},d_{FP})$, $n\geq 4$).

If $n\geq 4$, balls in the metric space of embedded paths
$(\Pi_{\mathcal{E}},d_{FP})$ in $\mathbb{R}^{n}$ are path-connected.

######  Proof B.13.

Let $[\gamma_{0}],[\gamma_{1}],[\gamma_{2}]\in\Pi_{\mathcal{E}}$ in the
ambient space $\mathbb{R}^{n}$, for $n\geq 4$. Let $\delta>0$, and
$\mathbb{B}:=\mathbb{B}_{d_{FG}}([\gamma_{0}],\delta)\subset\Pi_{\mathcal{E}}$.
Since all topological knots are represented equivalently in only three
dimensions, without loss of generality, we consider the projections of every
$\gamma_{0}\in[\gamma_{0}],\gamma_{1}\in[\gamma_{1}]$, and
$\gamma_{2}\in[\gamma_{2}]$ in $\mathbb{R}^{3}$. Construct a continuous
$\Gamma:[0,1]\to\Pi_{\mathcal{E}}$ by the linear interpolation from
$\Gamma(0)=\gamma_{1}$ to $\Gamma(1)=\gamma_{2}$. By the rectifiability of the
embeddings $\gamma_{1}$ and $\gamma_{2}$, the interpolation must reduce
$d_{FP}(\gamma_{1},\gamma_{2})$ by some $\epsilon>0$ before a self-crossing is
required in the image of $\Gamma_{t}$ at some $t\in[0,1]$.

At $t$, conduct a self-crossing by perturbing $\Gamma_{t}$ in the fourth
dimension by no more than $\epsilon/2$. This increases
$d_{FP}(\Gamma_{t},\gamma_{2})$ by no more than $\epsilon/2$. Hence,
$d_{FP}(\Gamma_{t},\gamma_{2})$ is either strictly decreasing as $t\to 1$, or
necessarily satisfies $d_{FP}(\Gamma_{t},\gamma_{2})\leq\delta-\epsilon/2$ for
$\epsilon>0$. This is to say, for all $t\in[0,1]$,
$d_{FP}(\Gamma_{t},\gamma_{2})\leq\delta$, and $\Gamma_{t}\in\mathbb{B}$.
Hence, metric balls in the space are path-connected.