# Vietoris–Rips Complexes of Metric Spaces near a Metric Graph

Sushovan Majhi  University of California, Berkeley, USA<EMAIL_ADDRESS>
###### Abstract.

For a sufficiently small scale $\beta>0$, the Vietoris–Rips complex
$\mathcal{R}_{\beta}(S)$ of a metric space $S$ with a small Gromov–Hausdorff
distance to a closed Riemannian manifold $M$ has been already known to recover
$M$ up to homotopy type. While the qualitative result is remarkable and
generalizes naturally to the recovery of spaces beyond Riemannian
manifolds—such as geodesic metric spaces with a positive convexity radius—the
generality comes at a cost. Although the scale parameter $\beta$ is known to
depend only on the geometric properties of the geodesic space, how to
quantitatively choose such a $\beta$ for a given geodesic space is still
elusive. In this work, we focus on the topological recovery of a special type
of geodesic space, called a metric graph. For an abstract metric graph
$\mathcal{G}$ and a (sample) metric space $S$ with a small Gromov–Hausdorff
distance to it, we provide a description of $\beta$ based on the convexity
radius of $\mathcal{G}$ in order for $\mathcal{R}_{\beta}(S)$ to be homotopy
equivalent to $\mathcal{G}$. Our investigation also extends to the study of
the Vietoris–Rips complexes of a Euclidean subset $S\subset\mathbb{R}^{d}$
with a small Hausdorff distance to an embedded metric graph
$\mathcal{G}\subset\mathbb{R}^{d}$. From the pairwise Euclidean distances of
points of $S$, we introduce a family (parametrized by $\varepsilon$) of path-
based Vietoris–Rips complexes $\mathcal{R}^{\varepsilon}_{\beta}(S)$ for a
scale $\beta>0$. Based on the convexity radius and distortion of the embedding
of $\mathcal{G}$, we show how to choose a suitable parameter $\varepsilon$ and
a scale $\beta$ such that $\mathcal{R}^{\varepsilon}_{\beta}(S)$ is homotopy
equivalent to $\mathcal{G}$.

##  1\. Introduction

We present in this article a satisfactory answer to our quest of understanding
the homotopy type of the Vietoris–Rips complexes of a metric space near a
metric graph (Definition 2.3). Given a metric space $(X,d_{X})$ and a positive
scale $\beta$, the Vietoris–Rips complex $\mathcal{R}_{\beta}(X)$ is defined
as an abstract simplicial complex having a $k$–simplex for every finite subset
of $X$ with cardinality $(k+1)$ and diameter less than $\beta$. The name
“Vietoris–Rips complex” was coined by Jean-Claude Hausmann in [15]. The notion
was first introduced by L. Vietoris (see [22]), then reintroduced and studied
by E. Rips in the context of hyperbolic groups, and later popularized by M.
Gromov under the name of Rips complex (see [13] for example).

The construction of the Vietoris–Rips complex $\mathcal{R}_{\beta}(X)$ can be
loosely thought of as the “fattening” of the metric space $X$ by an amount
$\beta$. Naturally for a well-behaved metric space $X$ and sufficiently small
scale $\beta$, the “fattened” $X$ is expected to be homotopy equivalent to
$X$. In [15], this intuition has been attested to by Hausmann: for
sufficiently small $\beta$, a closed Riemannian manifold $M$ is homotopy
equivalent to its Vietoris–Rips complex $\mathcal{R}_{\beta}(M)$. As a follow-
up question, Hausmann further speculates in [15, p. 183] if the Vietoris–Rips
complex of a (dense) _finite_ subset $S\subset M$ also retains the homotopy
type of $M$. In the remarkable work [17], Latschev provides a positive answer
to the question in a more general set-up, where $(S,d_{S})$ is taken to be an
abstract metric space and its density in $M$ is replaced by the
Gromov–Hausdorff distance to $M$. The author guarantees the existence of a
sufficiently small scale $\beta$, which depends only on $M$ and the
Gromov–Hausdorff distance between $M$ and $S$, such that
$\mathcal{R}_{\beta}(S)$ is homotopy equivalent to $M$. Despite the
qualitative guarantee in [17], it is not apparently clear how to
quantitatively choose such a small $\beta$ for a given Riemannian manifold.
The choice of a suitable $\beta$ is still elusive—it requires an explicit
knowledge of the curvature bounds of $M$. It is reasonable to ask if we can
quantitatively choose $\beta$ for some special cases.

Although the works of Hausmann ([15]) and Latschev ([17]) consider $M$ to be a
closed Riemannian manifold, the results hold true more generally for a
geodesic metric space with a positive convexity radius; see the remark [15, p.
179]. Roughly speaking, the convexity radius of a geodesic space is the radius
of the largest (geodesically) convex ball. A metric graph, denoted
${\mathcal{G}}$ throughout the paper, is a special type of geodesic space; see
Definition 2.3. In general, the study of the topology of the Vietoris–Rips
complexes of a metric space $S$ is very delicate. The intrinsic filamentary
structure and a positive convexity radius of ${\mathcal{G}}$, however,
facilitate such a pursuit when $S$ is assumed to be in a close proximity to
${\mathcal{G}}$. Our current study revolves around the recovery (up to
homotopy type) of a metric graph $({\mathcal{G}},d_{\mathcal{G}})$ from the
Vietoris–Rips complexes of a (sample) metric space $(S,d_{S})$ with a small
Gromov–Hausdorff and Hausdorff distance to ${\mathcal{G}}$.

###  1.1. Motivation

In the last decade, the Vietoris–Rips complexes have received a far and wide
popularity in the computational topology and topological data analysis (TDA)
community. In the shape reconstruction paradigm, for example, a point-cloud
can be modeled as a finite metric space $(S,d_{S})$ sampled around an unknown
_shape_ $(X,d_{X})$. The objective then is to _learn_ the topology of $X$ by
studying different simplicial complexes of $S$. Some of the popular choices
are Vietoris–Rips complex, Čech complex, witness complex [20], alpha complex
[11], etc. In many applications, the Vietoris–Rips complexes are deemed a
better alternative to the conventional Čech complexes. The computational
scheme of Čech complexes is not well-understood and requires an explicit
knowledge of the ambient metric space, while the Vietoris–Rips complexes can
be computed just from the pairwise distances of points of $S$.

The topological reconstruction of an embedded smooth manifold—more generally
spaces with a positive reach—using the Vietoris–Rips complexes has been
studied, for example, in [4, 6, 9, 16]. Such results embolden us to employ the
Vietoris–Rips complexes in the recovery of spaces beyond the class of positive
reach. For an example of such a space, consider a graph embedded in the
Euclidean space. There is a wide spectrum of data-driven applications
requiring the reconstruction of a (hidden) graph, both abstract and embedded,
from a finite sample around it. Examples include road-map reconstruction from
GPS traces [5, 10], reconstruction of the filamentary trajectory of shock from
earthquake sensors [1], etc. Among the notable Vietoris–Rips inspired
reconstruction of metric graphs, we mention [2] and [12, 18] under the
Gromov–Hausdorff and Hausdorff sampling conditions, respectively.

###  1.2. Related Work

The current work is discerned to be closely related to and inspired by the
reconstruction of embedded geodesic spaces from a finite sample [12]. For a
Hausdorff–close sample $S$ around an embedded metric graph ${\mathcal{G}}$,
the authors note that the Euclidean Vietoris–Rips complex generally fails to
be homotopy equivalent to the underlying graph. It does not come as a
surprise—because a metric graph can have very sharp corners, moreover
Hausdorff density of the sample does not guarantee a small Gromov–Hausdorff
distance. The Euclidean Vietoris–Rips complex does not serve well as a
topologically faithful _reconstruction_ of the unknown graph. Instead of the
Euclidean metric, the Vietoris–Rips complexes of the sample under a family of
path-based metrics $(S,d^{\varepsilon})$ (also defined in Definition 4.4) is
introduced. Under this metric, the Vietoris–Rips complex
$\mathcal{R}^{\varepsilon}_{\beta}(S)$ and the underlying graph
${\mathcal{G}}$ are shown to have isomorphic fundamental groups; see [12,
Theorem 4.3]. We further investigate this metric to find that the result holds
for higher homotopy groups as well, as previously conjectured in [12]. In this
context, we also mention the works of [3, 4], where the homotopy equivalence
results of Hausmann [15] and Latschev [17] have been recast in the light of an
alternative metric, called the Vietoris–Rips thickening, in order to
additionally retain the metric structure.

###  1.3. Our Contribution

One of the major contributions of this work is to unravel the scale parameter
at which the Vietoris–Rips complex of a sample $S$ recovers (up to homotopy
type) a metric graph, under both the Gromov–Hausdorff and Hausdorff sampling
conditions. The work also claims novelty in presenting the barycentric
subdivision (defined in Section 2) as a critical ingredient in the proofs of
our main homotopy equivalence results Theorem 3.8 and Theorem 4.13. The paper
is organized in the following manner. Section 2 delineates the definitions,
notations, and known results that are frequently used throughout the paper. In
Section 3, the recovery of an abstract metric graph from a Gromov–Hausdorff
close sample is presented. Whereas, Section 4 is devoted to the study of the
path-based metric and the homotopy equivalence results for an embedded graph
from a Hausdorff close Euclidean sample.

##  2\. Preliminaries

In this section, we present definitions and notations that we use throughout
the paper. The useful results from algebraic topology are stated here without
a proof; details can be found any standard textbook on the subject, e.g., [19,
21].

###  2.1. Metric Spaces

Let $(X,d_{X})$ be a metric space. When it is clear from the context, we omit
the metric $d_{X}$ from the notation, and denote the metric space just by $X$.
For any center $c\in X$ and radius $r\geq 0$, the (open) metric ball in
$(X,d_{X})$ is denoted by ${\mathbb{B}}_{X}(c,r)$. The diameter, denoted
$\mathrm{diam}_{X}\mathopen{}\mathclose{{}\left(Y}\right)$, of a subset
$Y\subset X$ is defined by the supremum of the pairwise distances in $Y$.

$\mathrm{diam}_{d_{X}}\mathopen{}\mathclose{{}\left(Y}\right)\stackrel{{\scriptstyle
def}}{{=}}\sup_{y_{1},y_{2}\in Y}d_{X}(y_{1},y_{2}).$

When $Y$ is compact, its diameter is finite.

A correspondence $\mathcal{C}$ between two (non-empty) metric spaces
$(X,d_{X})$ and $(Y,d_{Y})$ is defined to be a subset of $X\times Y$ such that

  1. (a)

for any $x\in X$, there exists $y\in Y$ such that $(x,y)\in\mathcal{C}$, and

  2. (b)

for any $y\in Y$, there exists $x\in X$ such that $(x,y)\in\mathcal{C}$.

We denote the set of all correspondences between $X,Y$ by $\mathcal{C}(X,Y)$.
Note that the definition of correspondence does not depend on the metric space
structure on the sets, however we can define the distortion of a
correspondence using the metrics on them. For a correspondence
$\mathcal{C}\in\mathcal{C}(X,Y)$, its _distortion_ is defined as follows:

$\mathrm{dist}(\mathcal{C})\stackrel{{\scriptstyle\text{def}}}{{=}}\sup_{(x_{1},y_{1}),(x_{2},y_{2})\in\mathcal{C}}\big{\lvert}d_{X}(x_{1},x_{1})-d_{Y}(y_{1},y_{2})\big{\rvert}.$

For $\varepsilon>0$, a correspondence is called an _$\varepsilon$
-correspondence_ if its distortion is less than $\varepsilon$.

######  Definition 2.1 (Gromov-Hausdorff Distance).

Let $(X,d_{X})$ and $(Y,d_{Y})$ be two compact metric spaces. The _Gromov-
Hausdorff_ distance between $X$ and $Y$, denoted by $d_{GH}(X,Y)$, is defined
as follows:

$d_{GH}(X,Y)\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{2}\mathopen{}\mathclose{{}\left[\inf_{\mathcal{C}\in\mathcal{C}(X,Y)}\mathrm{dist}(\mathcal{C})}\right].$

###  2.2. Simplicial Complexes

An _abstract simplicial complex_ ${\mathcal{K}}$ is a collection of finite
sets such that if $\sigma\in{\mathcal{K}}$, then so are all its non-empty
subsets. In general, elements of ${\mathcal{K}}$ are called _simplices_ of
${\mathcal{K}}$. The singleton sets in ${\mathcal{K}}$ are called the
_vertices_ of ${\mathcal{K}}$. If a simplex $\sigma\in{\mathcal{K}}$ has
cardinality $(q+1)$, then it is called a _$q$ -simplex_ and is denoted by
$\sigma_{k}$. A $k$–simplex $\sigma_{k}$ is also written as
$[v_{0},v_{1},\ldots,v_{k}]$, where $v_{i}$’s belong to the vertex set of
${\mathcal{K}}$. If $\sigma^{\prime}$ is a (proper) subset of $\sigma$, then
$\sigma^{\prime}$ is called a (proper) _face_ of $\sigma$, written as
$\sigma^{\prime}\prec\sigma$.

Let ${\mathcal{K}}_{1}$ and ${\mathcal{K}}_{2}$ be abstract simplicial
complexes with vertex sets $V_{1}$ and $V_{2}$, respectively. A _vertex map_
is a map between the vertex sets. Let $\phi\colon V_{1}\to V_{2}$ be a vertex
map. We say that $\phi$ induces a _simplicial map_
$\phi:{\mathcal{K}}_{1}\to{\mathcal{K}}_{2}$ if for all
$\sigma_{k}=[v_{0},v_{1},\ldots,v_{k}]\in K_{1}$, the image

$\phi(\sigma_{k})\stackrel{{\scriptstyle
def}}{{=}}[\phi(v_{0}),\phi(v_{1}),\ldots,\phi(v_{k})]\in{\mathcal{K}}_{2}.$

Two simplicial maps $\phi,\psi:{\mathcal{K}}_{1}\to{\mathcal{K}}_{2}$ are
called _contiguous_ if for every simplex $\sigma_{1}\in{\mathcal{K}}_{1}$,
there exists a simplex $\sigma_{2}\in{\mathcal{K}}_{2}$ such that
$\phi(\sigma_{1})\cup\psi(\sigma_{1})\prec\sigma_{2}$.

For an abstract simplicial complex ${\mathcal{K}}$ with vertex set $V$, one
can define its _geometric complex_ or _underlying topological space_ , denoted
by $\big{\lvert}{\mathcal{K}}\big{\rvert}$, as the space of all functions
$h:V\to[0,1]$ satisfying the following two properties:

  1. (i)

$\mathrm{supp}{(}h)\stackrel{{\scriptstyle def}}{{=}}\\{v\in V\mid h(v)\neq
0\\}$ is a simplex of ${\mathcal{K}}$, and

  2. (ii)

$\sum\limits_{v\in\mathcal{V}}h(v)=1$.

For $h\in\big{\lvert}{\mathcal{K}}\big{\rvert}$ and vertex $v$ of
${\mathcal{K}}$, the real number $h(v)$ is called the $v$–th _barycentric
coordinate_ of $h$. For a simplex $\sigma$ of ${\mathcal{K}}$, its _closed
simplex_ $\big{\lvert}\sigma\big{\rvert}$ and _open simplex_
$\mathopen{}\mathclose{{}\left\langle\sigma}\right\rangle$ are subsets of
$\big{\lvert}{\mathcal{K}}\big{\rvert}$ defined as follows:

$\big{\lvert}\sigma\big{\rvert}\stackrel{{\scriptstyle
def}}{{=}}\mathopen{}\mathclose{{}\left\\{h\in\big{\lvert}{\mathcal{K}}\big{\rvert}\mid\mathrm{supp}{(}h)\subset\sigma}\right\\},\text{and
}\mathopen{}\mathclose{{}\left\langle\sigma}\right\rangle\stackrel{{\scriptstyle
def}}{{=}}\mathopen{}\mathclose{{}\left\\{h\in\big{\lvert}{\mathcal{K}}\big{\rvert}\mid\mathrm{supp}{(}h)=\sigma}\right\\}.$

A simplex $\sigma$ of ${\mathcal{K}}$ is called the _carrier_ of a subset
$A\subset\big{\lvert}{\mathcal{K}}\big{\rvert}$ if $\sigma$ is the unique
smallest simplex such that $A\subset\big{\lvert}\sigma\big{\rvert}$. In this
work, we use the standard metric topology on $|{\mathcal{K}}|$, as defined in
[21]. A simplicial map $\phi:{\mathcal{K}}_{1}\to{\mathcal{K}}_{2}$ induces a
continuous (in this topology) map
$\big{\lvert}\phi\big{\rvert}:\big{\lvert}{\mathcal{K}}_{1}\big{\rvert}\to\big{\lvert}{\mathcal{K}}_{2}\big{\rvert}$
defined by

$\big{\lvert}\phi\big{\rvert}(h)(v^{\prime})\stackrel{{\scriptstyle
def}}{{=}}\sum\limits_{\phi(v)=v^{\prime}}h(v),\text{ for
}v^{\prime}\in{\mathcal{K}}_{2}.$

From the above definition, it is not difficult to see that
$\big{\lvert}\phi\big{\rvert}(h)\in\big{\lvert}h(\sigma)\big{\rvert}$ whenever
$h\in\mathopen{}\mathclose{{}\left\langle\sigma}\right\rangle$.

###  2.3. Barycentric Subdivision

The _barycenter_ , denoted $b(\sigma_{k})$, of a $k$–simplex
$\sigma_{k}=[v_{0},v_{1},\ldots,v_{k}]$ of ${\mathcal{K}}$ is the point of
$\mathopen{}\mathclose{{}\left\langle\sigma_{k}}\right\rangle$ such that
$\widehat{\sigma_{k}}(v_{i})=\frac{1}{k+1}$ for all $0\leq i\leq k$. Using
linearity of simplices, a more convenient way of writing this is:

$\widehat{\sigma_{k}}=\sum_{i=0}^{k}\frac{1}{k+1}v_{i}.$

Let ${\mathcal{K}}$ be a complex. A _subdivision_ of ${\mathcal{K}}$ is a
simplicial complex ${\mathcal{K}}^{\prime}$ such that

  1. (1)

the vertices of ${\mathcal{K}}^{\prime}$ are points of
$\big{\lvert}{\mathcal{K}}\big{\rvert}$,

  2. (2)

if $s^{\prime}$ is a simplex of ${\mathcal{K}}^{\prime}$, then there is
$s\in{\mathcal{K}}$ such that $s^{\prime}\subset\big{\lvert}s\big{\rvert}$,
and

  3. (3)

the linear map
$h:\big{\lvert}{\mathcal{K}}^{\prime}\big{\rvert}\to\big{\lvert}{\mathcal{K}}\big{\rvert}$
sending each vertex of ${\mathcal{K}}^{\prime}$ to the corresponding point of
$\big{\lvert}{\mathcal{K}}\big{\rvert}$ is a homeomorphism.

The _barycentric subdivision_ of a simplicial complex ${\mathcal{K}}$ is a
special subdivision, and is denoted by
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$. The vertices
of $\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ are the
barycenters of the simplices of ${\mathcal{K}}$. The simplices of
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ are (non-
empty) finite sets
$[\widehat{\sigma_{0}},\widehat{\sigma_{1}},\ldots,\widehat{\sigma_{k}}]$ such
that $\sigma_{i-1}\prec\sigma_{i}$ for $1\leq i\leq k$. If
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ is further
subdivided, we denote the barycentric subdivision of
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ by
$\mathrm{sd}^{2}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$, and so
on. With the definition of the barycentric subdivision at our disposal, we now
prove the following fact, which becomes indispensible for the proofs of Lemma
3.7 and Lemma 4.12.

######  Proposition 2.2 (Commuting Diagram).

Let ${\mathcal{K}}$ be a $k$–dimensional simplicial complex and
${\mathcal{L}}$ a flag complex. Let
$f:~{}{\mathcal{K}}\xrightarrow{\quad\quad}{\mathcal{L}}$ and
$g:\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\xrightarrow{\quad\quad}{\mathcal{L}}$
be simplicial maps such that

  1. (a)

$g(v)=f(v)$ for every vertex $v$ of ${\mathcal{K}}$,

  2. (b)

$f(\sigma)\cup g(\widehat{\sigma})$ is a simplex of ${\mathcal{L}}$ whenever
$\sigma$ is a simplex of ${\mathcal{K}}$.

Then, the following diagram commutes up to homotopy:

$\big{\lvert}\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$$\big{\lvert}{\mathcal{K}}\big{\rvert}$$\big{\lvert}{\mathcal{L}}\big{\rvert}$$h^{-1}$$\big{\lvert}g\big{\rvert}$$\big{\lvert}f\big{\rvert}$

where $h$ is a linear homeomorphism sending each vertex of
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ to the
corresponding point of $\big{\lvert}{\mathcal{K}}\big{\rvert}$.

###### Proof.

We show that the maps $\big{\lvert}g\big{\rvert}$ and
$\mathopen{}\mathclose{{}\left(\big{\lvert}f\big{\rvert}\circ h}\right)$ are
homotopic by constructing an explicit homotopy
$H:~{}\big{\lvert}\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}\times[0,1]\xrightarrow{\quad\quad}\big{\lvert}{\mathcal{L}}\big{\rvert}$
with $H(\cdot,0)=g(\cdot)$ and
$H(\cdot,1)=\mathopen{}\mathclose{{}\left(\big{\lvert}f\big{\rvert}\circ
h}\right)(\cdot)$. The commutativity of the diagram then follows, since $h$ is
a homeomorphism.

The complex ${\mathcal{K}}$ is taken to be $k$–dimensional. Without any loss
of generality, we can assume that every point of
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ belongs to a
$k$–simplex. Take an arbitrary
$x\in\big{\lvert}\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$.
We can write $x$ in its barycentric coordinates as
$x=\sum_{i=0}^{k}\zeta_{i}\widehat{\sigma_{i}}$, where
$\sigma_{k}=[a_{0},a_{1},\ldots,a_{k}]$ is a $k$–simplex of ${\mathcal{K}}$
and $\sigma_{i}=[a_{0},a_{1},\ldots,a_{i}]$ for $0\leq i\leq k$. Consider a
partition

$0=t_{0}<t_{1}<\ldots<t_{k}=1$

of $[0,1]$. We first define the homotopy $H(\cdot,t)$ at $t=t_{i}$ for
$i=0,1,\ldots,k$, and then argue that we can _interpolate_ $H$ continuously
(using the straight-line homotopy) for any $t\in[t_{i-1},t_{i}]$. For any
$0\leq i\leq k$, define

(1)
$H(x,t_{i})=\sum_{j=0}^{i}\zeta_{j}\mathopen{}\mathclose{{}\left(\big{\lvert}f\big{\rvert}\circ
h}\right)(\widehat{\sigma_{j}})+\sum_{j=i+1}^{k}\zeta_{j}\big{\lvert}g\big{\rvert}(\widehat{\sigma_{j}}).$

From the above definition, we note for $i=0$ that

$H(x,0)=\zeta_{0}\mathopen{}\mathclose{{}\left(\big{\lvert}f\big{\rvert}\circ
h}\right)(\widehat{\sigma_{0}})+\sum_{j=1}^{k}\zeta_{j}\big{\lvert}g\big{\rvert}(\widehat{\sigma_{j}})=\zeta_{0}\big{\lvert}g\big{\rvert}(\widehat{\sigma_{0}})+\sum_{j=1}^{k}\zeta_{j}\big{\lvert}g\big{\rvert}(\widehat{\sigma_{j}})=\sum_{j=0}^{k}\zeta_{j}\big{\lvert}g\big{\rvert}(\widehat{\sigma_{j}})=\big{\lvert}g\big{\rvert}(x).$

The second equality is due to condition (a) and fact that $\sigma_{0}$ is a
vertex ${\mathcal{K}}$. Also, for $i=k$ we note that

$H(x,1)=\sum_{j=0}^{k}\zeta_{j}\mathopen{}\mathclose{{}\left(\big{\lvert}f\big{\rvert}\circ
h}\right)(\widehat{\sigma_{j}})=\mathopen{}\mathclose{{}\left(\big{\lvert}f\big{\rvert}\circ
h}\right)\mathopen{}\mathclose{{}\left(\sum_{j=0}^{k}\zeta_{j}\widehat{\sigma_{j}}}\right)=\mathopen{}\mathclose{{}\left(\big{\lvert}f\big{\rvert}\circ
h}\right)(x).$

The second equality is due to the fact that $h$ is a linear homeomorphism.

We now fix $0\leq i\leq k$, and extend the definition of $H(x,t)$ for any
$t\in[t_{i-1},t_{i}]$ by using the straight-line joining $H(x,t_{i-1})$ and
$H(x,t_{i})$. In order for the straight line joining them to be well-defined,
we show that both $H(x,t_{i-1})$ and $H(x,t_{i})$ belong to
$\big{\lvert}\eta\big{\rvert}$ for some simplex $\eta$ of ${\mathcal{L}}$. The
fact that the geometric realization of a simplex is always convex, would then
validate the continuous extension of $H(\cdot,t)$.

We define

$\eta\stackrel{{\scriptstyle def}}{{=}}f(\sigma_{i})\cup
g([\widehat{\sigma_{i}},\widehat{\sigma_{i+1}},\ldots,\widehat{\sigma_{k}}]).$

Since $f,g$ are simplicial maps and ${\mathcal{L}}$ is a flag complex,
condition (b) implies that $\eta$ is a simplex of ${\mathcal{L}}$. From the
definition (1) and the fact that
$h(\widehat{\sigma_{l}})\in\big{\lvert}\sigma_{i}\big{\rvert}$ for all $0\leq
l\leq i$, we conclude that both $H(x,t_{i-1})$ and $H(x,t_{i})$ belong to
$\big{\lvert}\eta\big{\rvert}$. So, $H(x,t)$ is well-defined and continuous
for $t\in[t_{i-1},t_{i}]$. Moreover, the images agree at the endpoints as
noted from (1). Therefore, $H$ defines the desired homotopy. ∎

###  2.4. Metric Graphs

We follow [7] to define a metric graph. We always denote a metric graph by
${\mathcal{G}}$ in this following sections.

######  Definition 2.3 (Metric Graph).

A metric space $({\mathcal{G}},d_{\mathcal{G}})$ is called a _metric graph_ if
there are a non-empty set $V$, an equivalence relation $\mathcal{R}$ on $V$,
and a collection $E$ of metric segments111a metric segment is a metric space
isometric to a real line segment $[0,a]$ for $a\geq 0$. with their endpoints
in $V$ such that ${\mathcal{G}}$ is homeomorphic to the quotient space

$\mathopen{}\mathclose{{}\left(\bigsqcup_{e\in E}e}\right)/\sim\mathcal{R}.$

The metric segments $e\in E$ are called the _edges_ and the equivalence
classes of their endpoints in $V$ are called the _vertices_ of
${\mathcal{G}}$. For of an edge $e\in E$, its length $L(e)$ is the length of
the corresponding metric segment. Note that the length can be different from
the distance of the endpoint of $e$ in the $d_{\mathcal{G}}$ metric. Extending
the definition of length for a continuous path $\gamma:[0,1]\to{\mathcal{G}}$,
we define the length $L(\gamma)$ as the sum of the lengths of the (full or
partial) edges that $\gamma$ consists of. A metric graph ${\mathcal{G}}$,
therefore, is endowed with two layers of information: a metric structure
turning it into a length space [7, Definition 2.1.6] and a combinatorial
structure $(V,E)$ as an abstract graph. Using the above definition, we are
also allowing ${\mathcal{G}}$ to have loops or single edge cycles. In this
paper, we only consider path-connected, locally-finite metric graphs
$({\mathcal{G}},d_{\mathcal{G}})$. As a consequence, $d_{\mathcal{G}}$ is a
finite metric and the degree of any vertex of $G$ is finite.

For a pair of points $a,b\in{\mathcal{G}}$, there always exists a _shortest
path_ or _geodesic path_ $\gamma$ in ${\mathcal{G}}$ joining $a,b$ such that
the length $L(\gamma)=d_{\mathcal{G}}(a,b)$.

######  Definition 2.4 (Convexity Radius).

Let $({\mathcal{G}},d_{\mathcal{G}})$ be a metric graph. We define the
convexity radius of ${\mathcal{G}}$, denoted $\rho({\mathcal{G}})$, to be the
largest number $r\geq 0$ with the following property: if $a,b\in{\mathcal{G}}$
with $d_{\mathcal{G}}(a,b)\leq 2r$, then there is a unique geodesic in
${\mathcal{G}}$ joining $a$ and $b$.

For a path-connected graph ${\mathcal{G}}$ with finitely many vertices, the
convexity radius $\rho({\mathcal{G}})$ is always positive. If $e_{s}$ is a
shortest edge, then $\rho({\mathcal{G}})\geq\frac{1}{4}L(e_{s})$. The equality
holds when $e_{s}$ forms a self-loop in ${\mathcal{G}}$. The convexity radius
can be defined for a more general geodesic spaces; see [15] for example. It
can be shown that the convexity radius of a closed Riemannian manifold is also
positive. Note that there are geodesic spaces with vanishing convexity radius.
When it is positive, however, we have the following remarkable theorem by
Hausmann. Although the result holds for more general spaces, we state it here
in the context of metric graphs.

######  Theorem 2.5 (Hausmann’s Theorem[15]).

Let $({\mathcal{G}},d_{\mathcal{G}})$ be a metric graph with a positive
convexity radius $\rho({\mathcal{G}})$. Then, for any
$0<\alpha<\rho({\mathcal{G}})$, the geometric complex of
$\mathcal{R}_{\alpha}({\mathcal{G}})$ is homotopy equivalent to
${\mathcal{G}}$.

##  3\. Abstract Metric Graphs

Let $({\mathcal{G}},d_{\mathcal{G}})$ be a path-connected (abstract) metric
graph with a positive convexity radius $\rho({\mathcal{G}})$. This section is
devoted to the study of the Vietoris–Rips complexes of a metric space
$(S,d_{S})$ that is close to ${\mathcal{G}}$ in the Gromov-Hausdorff distance
(see Definition 2.1). Our main result of this section is presented in Theorem
3.8. We show how to choose a scale $\beta$, depending on the Gromov-Hausdorff
distance $d_{GH}(S,{\mathcal{G}})$ and $\rho({\mathcal{G}})$, such that the
Vietoris–Rips complex the geometric complex of $\mathcal{R}_{\beta}(S)$ is
homotopy equivalent to ${\mathcal{G}}$.

Our technique of the proof involves the use of the barycentric subdivision of
the Vietoris–Rips complexes of $S$. The approach uses the concept of
circumcenter in metric space—especially in ${\mathcal{G}}$. In Subsection 3.1,
we define the notion, and observe that _small_ subsets of ${\mathcal{G}}$ have
a unique circumcenter. We present the final homotopy equivalence result of
this section in Subsection 3.2.

###  3.1. Circumcenters in ${\mathcal{G}}$

We begin with the definition of circumcenter in a metric space. For the
definition, we follow [7].

######  Definition 3.1 (Circumcenter).

Let $(X,d_{X})$ be a metric space and $Y\subset X$ a bounded set. A
_circumscribed ball_ of $Y$ is a (closed) metric ball of minimal radius among
the balls containing $Y$. The radius of a circumscribed ball is called the
_circumradius_ and the center a _circumcenter_ $Y$, denote by
$\theta\mathopen{}\mathclose{{}\left(Y}\right)$.

A circumcenter may not always exist for subsets of a metric space. Even if it
exists, it may not be unique for some subsets. When the diameter of a compact
subset $Y$ of ${\mathcal{G}}$ is less that $\rho({\mathcal{G}})$, however, its
circumcenter exists uniquely. For an example, consider a pair of antipodal
points as a bounded subset of a circle.

######  Proposition 3.2 (Circumcenters in Metric Graphs).

Let $Y\subset{\mathcal{G}}$ be a (non-empty) compact subset with
$\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right)<2\rho({\mathcal{G}})$.
Then, the circumcenter of $Y$ exists uniquely. Moreover, the circumradius is
$\frac{1}{2}\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right)$.

###### Proof.

Since $Y$ is compact, there exist $y_{1},y_{2}\in Y$ such that
$\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right)=d_{\mathcal{G}}(y_{1},y_{2})$.
From $d_{\mathcal{G}}(y_{1},y_{2})<2\rho({\mathcal{G}})$, it follows that
there is a unique geodesic in ${\mathcal{G}}$ joining $y_{1}$ and $y_{2}$;
call it $\gamma$. We claim that the midpoint $m$ of $\gamma$ is the unique
circumcenter of $Y$, and that the circumradius is
$r=\frac{1}{2}d_{\mathcal{G}}(y_{1},y_{2})$.

The proof becomes trivial if there exists an edge $e$ of ${\mathcal{G}}$ such
that $\gamma\subset e$. In that case, $Y$ is fully contained in $e$. As a
result, $m$ is the unique circumcenter.

$e_{1}$$e_{2}$$e$$\vdots$$\vdots$$v$$m$$y_{1}$$y_{2}$$y$ Figure 1. The star
$\textbf{st}(v)$ of the vertex $v$ is shown by the red point. The dashed black
lines indicate some of the incident edges including $e_{1},e_{2}$, and $e$.
And, the thick blue line is the geodesic $\gamma$.

We now assume the case when $\gamma$ is contained in two edges $e_{1},e_{2}$
of ${\mathcal{G}}$ incident to a vertex $v$; the configuration is depicted in
Figure 1. Again from
$\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right)<2\rho({\mathcal{G}})$,
we note that $Y\subset\textbf{st}(v)$. To see that
$Y\subset\overline{{\mathbb{B}}_{{\mathcal{G}}}(m,r)}$, take any $y\in Y$ and
consider the following two sub-cases.

If $y$ lies on either $e_{1}$ or $e_{2}$, it has to lie on $\gamma$.
Otherwise,
$\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right)>d_{\mathcal{G}}(y_{1},y_{2})$—a
contradiction. We must have that $y\in\gamma$, consequently
$y\in\overline{{\mathbb{B}}_{{\mathcal{G}}}(m,r)}$.

For the other sub-case, let $y$ lies on an edge $e$ of ${\mathcal{G}}$ other
than $e_{1},e_{2}$. Without any loss of generality, we can assume that the
midpoint $m$ of $\gamma$ lies on $e_{2}$. This is exactly the case considered
in Figure 1. We now note that $d_{\mathcal{G}}(y,v)\leq
d_{\mathcal{G}}(y_{1},v)$. If not, then

$d_{\mathcal{G}}(y,y_{2})=d_{\mathcal{G}}(y,v)+d_{\mathcal{G}}(v,y_{2})>d_{\mathcal{G}}(y_{1},v)+d_{\mathcal{G}}(v,y_{2})=d_{\mathcal{G}}(y_{1},y_{2}),$

again leading to a contradiction. Therefore, the triangle inequality implies

$d_{\mathcal{G}}(y,m)\leq d_{\mathcal{G}}(y,v)+d_{\mathcal{G}}(v,m)\leq
d_{\mathcal{G}}(y_{1},v)+d_{\mathcal{G}}(v,m)=\frac{1}{2}d_{\mathcal{G}}(y_{1},y_{2})=r.$

So, $y\in\overline{{\mathbb{B}}_{{\mathcal{G}}}(m,r)}$.

Considering the all the above case, we conclude that
$Y\subset\overline{{\mathbb{B}}_{{\mathcal{G}}}(m,r)}$. The uniqueness follows
from the observation that a circumcenter cannot lie outside $\gamma$. Hence,
the proof. ∎

After establishing uniqueness of circumcenters in ${\mathcal{G}}$, we make
another important observation about the mutual distances of the circumcenters.

######  Proposition 3.3 (Circumcenter Distances).

If $Y$ is a compact subset of ${\mathcal{G}}$ with
$\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right)<2\rho({\mathcal{G}})$,
then for any non-empty subset $Y^{\prime}\subset Y$, we have

$d_{\mathcal{G}}\mathopen{}\mathclose{{}\left(\theta\mathopen{}\mathclose{{}\left(Y^{\prime}}\right),\theta\mathopen{}\mathclose{{}\left(Y}\right)}\right)\leq\frac{1}{2}\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right).$

###### Proof.

In the proof of Proposition 3.2, we have seen that
$\theta\mathopen{}\mathclose{{}\left(Y^{\prime}}\right)$ is the (geodesic)
midpoint of two farthest points of $Y^{\prime}$. Let
$r=\frac{1}{2}\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right)$.
From Proposition 3.2, we note $Y^{\prime}\subset
Y\subset\overline{{\mathbb{B}}_{\mathcal{G}}(\theta\mathopen{}\mathclose{{}\left(Y}\right),r)}$.
Also, the metric ball
$\overline{{\mathbb{B}}_{\mathcal{G}}(\theta\mathopen{}\mathclose{{}\left(Y}\right),r)}$
is a geodesically convex subset of ${\mathcal{G}}$, due to the fact that
$r<\rho({\mathcal{G}})$. So, we have that
$\theta\mathopen{}\mathclose{{}\left(Y^{\prime}}\right)\in\overline{{\mathbb{B}}_{\mathcal{G}}(\theta\mathopen{}\mathclose{{}\left(Y}\right),r)}$.
Hence,
$d_{\mathcal{G}}(\theta\mathopen{}\mathclose{{}\left(Y^{\prime}}\right),\theta\mathopen{}\mathclose{{}\left(Y}\right))\leq
r=\frac{1}{2}\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(Y}\right)$.
∎

###  3.2. Homotopy Equivalence

We now assume that $(S,d_{S})$ is a metric space the Gromov-Hausdorff distance
$d_{GH}(Y,{\mathcal{G}})<\frac{\beta}{3}$ for some $\beta>0$. From the
definition of Gromov-Hausdorff distance (Definition 2.1), there must exist a
$\mathopen{}\mathclose{{}\left(\frac{\beta}{3}}\right)$–correspondence
$\mathcal{C}\in\mathcal{C}({\mathcal{G}},S)$. The correspondence induces a
(possibly non-continuous and non-unique) vertex map
$\phi:{\mathcal{G}}\xrightarrow{\quad\quad}S$ such that
$(a,\phi(a))\in\mathcal{C}$ for all $a\in{\mathcal{G}}$. The vertex map $\phi$
extends to a simplicial map:

(2)
$\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\xrightarrow{\quad\phi\quad}\mathcal{R}_{\beta}(S).$

To see that $\phi$ is a simplicial map, take a $k$–simplex
$\sigma_{k}=[a_{0},a_{1},\ldots,a_{k}]$ in
$\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})$. By the construction of the
Vietoris–Rips complex, we have $d_{\mathcal{G}}(a_{i},a_{j})<\frac{2\beta}{3}$
for any $0\leq i,j\leq k$. Since $\mathcal{C}$ is a
$\mathopen{}\mathclose{{}\left(\frac{\beta}{3}}\right)$–correspondence and
$(a,\phi(a))\in\mathcal{C}$ for all $a\in{\mathcal{G}}$, we have

$d_{S}(\phi(a_{i}),\phi(a_{j}))\leq
d_{\mathcal{G}}(a_{i},a_{j})+\frac{\beta}{3}<\frac{2\beta}{3}+\frac{\beta}{3}=\beta.$

So, the image $\phi(\sigma_{k})=[\phi(a_{0}),\phi(a_{1}),\ldots,\phi(a_{k})]$
is a simplex of $\mathcal{R}_{\beta}(S)$.

We show that the simplicial map $\phi$ is a homotopy equivalence. We show in
Lemma 3.7 and Lemma 3.6 that for any $k\geq 0$, the simplicial map $\phi$
induces an isomorphism between the $k$–th homotopy groups. The homotopy
equivalence of $\phi$ would then follow from the Whitehead’s theorem [14,
Theorem 4.5].

######  Remarks 3.4.

For the description and computation of homotopy groups, the consideration of
basepoint is deliberately ignored throughout this paper. Our laziness can be
tolerated, as the considered scale parameters are such that all the
Vietoris–Rips complexes used here are path-connected. We prove the claim in
the following proposition.

######  Proposition 3.5 (Path-connectedness).

Let $(S,d_{S})$ be a metric space and $\beta>0$ a number such that
$d_{GH}(S,{\mathcal{G}})<\beta$, then for any positive $\alpha$, the geometric
complex of $\mathcal{R}_{\alpha+\beta}(S)$ is path-connected.

###### Proof.

Let $a,b\in S$, then there exist points
$a^{\prime},b^{\prime}\in{\mathcal{G}}$ such that
$(a^{\prime},a),(b^{\prime},b)\in\mathcal{C}$, where
$\mathcal{C}\in\mathcal{C}({\mathcal{G}},S)$ is a $\beta$–correspondence.
Since ${\mathcal{G}}$ is assumed to be path-connected, so is
$\mathcal{R}_{\alpha}({\mathcal{G}})$. As a result, there exists a sequence
$\\{x_{i}^{\prime}\\}_{i=0}^{k+1}\subset{\mathcal{G}}$ forming a path in
$\mathcal{R}_{\alpha}({\mathcal{G}})$ joining $a^{\prime}$ and $b^{\prime}$.
In other words, $x_{0}^{\prime}=a^{\prime}$, $x_{k+1}^{\prime}=b^{\prime}$,
and $d_{\mathcal{G}}(x_{i}^{\prime},x_{i+1}^{\prime})<\alpha$ for $0\leq i\leq
k$. There is also a corresponding sequence $\\{x_{i}\\}_{i=0}^{k+1}\subset S$
such that $x_{0}=a$, $x_{k+1}=b$, and $(x_{i}^{\prime},x_{i})\in\mathcal{C}$
for all $i$. We note that

$d_{S}(x_{i},x_{i+1})\leq
d_{\mathcal{G}}(x_{i}^{\prime},x_{i+1}^{\prime})+\beta<\alpha+\beta.$

So, the sequence $\\{x_{i}\\}$ produces a path in
$\mathcal{R}_{\alpha+\beta}(S)$ joining $a$ and $b$. We conclude that the
geometric complex of $\mathcal{R}_{\alpha+\beta}(S)$ is path-connected. ∎

The following two lemmas prove that the simplicial map $\phi$ defined in (2)
induces injective and surjective homomorphisms on the homotopy groups.

######  Lemma 3.6 (Injectivity).

Let $(S,d_{S})$ be a metric space and $\beta>0$ a number such that

$3d_{GH}({\mathcal{G}},S)<\beta<\frac{3\rho({\mathcal{G}})}{4}.$

For any $k\geq 0$, the simplicial map
$\phi:\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\xrightarrow{\quad\quad}\mathcal{R}_{\beta}(S)$
(as defined in (2)) induces an injective homomorphism on the $k$–th homotopy
group.

###### Proof.

Since $d_{GH}({\mathcal{G}},S)<\frac{\beta}{3}$, let us assume that
$\mathcal{C}\in\mathcal{C}({\mathcal{G}},S)$ be a
$\mathopen{}\mathclose{{}\left(\frac{\beta}{3}}\right)$–correspondence. We
note the following chain of simplicial maps:

$\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\xrightarrow{\quad\phi\quad}\mathcal{R}_{\beta}(S)\xrightarrow{\quad\psi\quad}\mathcal{R}_{\frac{4\beta}{3}}({\mathcal{G}}),$

such that $(a,\phi(a))\in\mathcal{C}$ for all $a\in{\mathcal{G}}$ and
$(\psi(b),b)\in\mathcal{C}$ for all $b\in S$.

There is also the natural inclusion
$\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\xhookrightarrow{\quad
i\quad}\mathcal{R}_{\frac{4\beta}{3}}({\mathcal{G}})$. We first claim that
$(\psi\circ\phi)$ and $i$ are contiguous. To prove the claim, take a
$l$–simplex $\sigma_{k}=[a_{0},a_{1},\ldots,a_{l}]$ in
$\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})$. So,
$d_{\mathcal{G}}(a_{i},a_{j})<\frac{2\beta}{3}$ for all $0\leq i,j\leq l$. We
then have

$\displaystyle d_{\mathcal{G}}((\psi\circ\phi)(a_{i}),a_{j})$
$\displaystyle=d_{\mathcal{G}}(\psi(\phi(a_{i})),a_{j})$ $\displaystyle\leq
d_{S}(\phi(a_{i}),\phi(a_{j}))+\frac{\beta}{3}$ $\displaystyle\leq
d_{\mathcal{G}}(a_{i},a_{j})+\frac{\beta}{3}+\frac{\beta}{3}$
$\displaystyle<\frac{2\beta}{3}+\frac{2\beta}{3}=\frac{4\beta}{3}$

This implies that $(\psi\circ\phi)(\sigma_{l})\cup i(\sigma_{l})$ is a simplex
of $\mathcal{R}_{\frac{4\beta}{3}}({\mathcal{G}})$. Since $\sigma_{l}$ is an
arbitrary simplex, the simplicial maps $(\psi\circ\phi)$ and $i$ are
contiguous. Consequently, the maps $\big{\lvert}\psi\circ\phi\big{\rvert}$ and
$\big{\lvert}i\big{\rvert}$ are homotopic.

Since $\frac{4\beta}{3}<\rho({\mathcal{G}})$, Theorem 2.5 implies that there
exist homotopy equivalences $T_{1},T_{2}$ such that the following diagram
commutes (up to homotopy):

$\big{\lvert}\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\big{\rvert}$$\big{\lvert}\mathcal{R}_{\frac{4\beta}{3}}({\mathcal{G}})\big{\rvert}$${\mathcal{G}}$$\big{\lvert}i\big{\rvert}$$\big{\lvert}T_{1}\big{\rvert}$$\big{\lvert}T_{2}\big{\rvert}$

So, $\big{\lvert}i\big{\rvert}$ is also a homotopy equivalence. Hence, the
induced homomorphism $\big{\lvert}i\big{\rvert}_{*}$ on the homotopy groups is
an isomorphism. On the other hand, we already have
$\big{\lvert}i\big{\rvert}\simeq\big{\lvert}\psi\circ\phi\big{\rvert}$.
Therefore, the induced homomorphism
$\mathopen{}\mathclose{{}\left(\big{\lvert}\psi\big{\rvert}_{*}\circ\big{\lvert}\phi\big{\rvert}_{*}}\right)$
is also an isomorphism, implying that $\big{\lvert}\phi\big{\rvert}_{*}$ is an
injective homomorphism on
$\pi_{k}\mathopen{}\mathclose{{}\left(\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})}\right)$.
∎

In order show surjectivity on homotopy groups, we employ the idea of the
simplicial subdivision.

######  Lemma 3.7 (Surjectivity).

Let $(S,d_{S})$ a metric space and $\beta>0$ a number such that

$3d_{GH}({\mathcal{G}},S)<\beta<\frac{3\rho({\mathcal{G}})}{2}.$

Then for any $k\geq 0$, the simplicial map
$\phi:\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\xrightarrow{\quad\quad}\mathcal{R}_{\beta}(S)$
(as defined in (2)) induces a surjective homomorphism on the $k$–th homotopy
group.

###### Proof.

As observed in Proposition 3.5, both
$\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})$ and $\mathcal{R}_{\beta}(S)$
are path-connected. So, the result holds for $k=0$.

For $k\geq 1$, let us take an abstract simplicial complex ${\mathcal{K}}$ such
that $\big{\lvert}{\mathcal{K}}\big{\rvert}$ is a triangulation of the
$k$-dimensional sphere ${\mathbb{S}}^{k}$. In order to show surjectivity of
$\big{\lvert}\phi\big{\rvert}_{*}$ on
$\pi_{k}\mathopen{}\mathclose{{}\left(\big{\lvert}\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\big{\rvert}}\right)$,
we start with a simplicial map
$g:{\mathcal{K}}\xrightarrow{\quad\quad}\mathcal{R}_{\beta}(S)$, and argue
that there must exist a simplicial map
$\widetilde{g}:\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\xrightarrow{\quad\quad}\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})$
such that the following diagram commutes up to homotopy:

(3)
$\big{\lvert}\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\big{\rvert}$$\big{\lvert}\mathcal{R}_{\beta}(S)\big{\rvert}$$\big{\lvert}{\mathcal{K}}\big{\rvert}$$\big{\lvert}\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$$\big{\lvert}\phi\big{\rvert}$$\big{\lvert}g\big{\rvert}$$\big{\lvert}\widetilde{g}\big{\rvert}$$h^{-1}$

where the linear homeomorphism
$h:\big{\lvert}\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}\xrightarrow{\quad\quad}\big{\lvert}{\mathcal{K}}\big{\rvert}$
maps each vertex of
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ to the
corresponding point of $\big{\lvert}{\mathcal{K}}\big{\rvert}$ as discussed in
Section 2.

We note that each vertex of
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ is the
barycenter, $\widehat{\sigma}$, of a simplex $\sigma$ of ${\mathcal{K}}$. In
order to construct the simplicial map
$\widetilde{g}:\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\xrightarrow{\quad\quad}\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})$,
we define it on the vertices of
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ first, and
prove that the vertex map extends to a simplicial map. Let
$\sigma_{l}=[a_{0},a_{1},\ldots,a_{l}]$ be an $l$–simplex of ${\mathcal{K}}$.
Since $g$ is a simplicial map, then the image
$g(\sigma_{l})=[g(a_{0}),g(a_{1}),\ldots,g(a_{l})]$ is a simplex of
$\mathcal{R}_{\beta}(S)$, hence a subset of $S$ with
$\mathrm{diam}_{S}\mathopen{}\mathclose{{}\left(g(\sigma_{l})}\right)<\beta$.
For each $0\leq i\leq l$, there exists $a_{i}^{\prime}\in{\mathcal{G}}$ such
that $(a_{i}^{\prime},g(a_{i}))\in\mathcal{C}$ for a
$\mathopen{}\mathclose{{}\left(\frac{\beta}{3}}\right)$–correspondence
$\mathcal{C}\in\mathcal{C}({\mathcal{G}},S)$. For $0\leq i\leq l$, we denote
$\sigma_{i}^{\prime}=\\{a_{0}^{\prime},a_{1}^{\prime},\ldots,a_{i}^{\prime}\\}\subset{\mathcal{G}}$.
Since $\mathcal{C}$ is a
$\mathopen{}\mathclose{{}\left(\frac{\beta}{3}}\right)$–correspondence, we
note for later that the diameter of the subset

(4)
$\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(\sigma_{i}^{\prime}}\right)\leq\mathrm{diam}_{S}\mathopen{}\mathclose{{}\left(g(\sigma_{i})}\right)+\frac{\beta}{3}<\beta+\frac{\beta}{3}=\frac{4\beta}{3}<2\rho({\mathcal{G}}).$

We then define the vertex map

$\widetilde{g}(\widehat{\sigma_{l}})\stackrel{{\scriptstyle
def}}{{=}}\theta\mathopen{}\mathclose{{}\left(\sigma_{l}^{\prime}}\right),$

where $\theta\mathopen{}\mathclose{{}\left(\sigma_{l}^{\prime}}\right)$ is the
circumcenter (see Definition 3.1) of $\sigma_{l}^{\prime}$. Due to the
diameter bound in (4), Proposition 3.2 implies that the circumcenter exists
uniquely. To see that $\widetilde{g}$ extends to a simplicial map, we consider
a typical $l$–simplex
$\tau_{l}=[\widehat{\sigma_{0}},\widehat{\sigma_{1}},\ldots,\widehat{\sigma_{l}}]$,
of $\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$, where
$\sigma_{i-1}\prec\sigma_{i}\prec\sigma_{l}$ for $1\leq i\leq l$. Now,

$\displaystyle\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(\widetilde{g}(\tau_{l})}\right)$
$\displaystyle=\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left([\theta\mathopen{}\mathclose{{}\left(\sigma_{0}^{\prime}}\right),\theta\mathopen{}\mathclose{{}\left(\sigma_{1}^{\prime}}\right),\ldots,\theta\mathopen{}\mathclose{{}\left(\sigma_{l}^{\prime}}\right)]}\right)$
$\displaystyle=\max_{0\leq i<j\leq
l}\\{d_{\mathcal{G}}(\theta\mathopen{}\mathclose{{}\left(\sigma_{i}^{\prime}}\right),\theta\mathopen{}\mathclose{{}\left(\sigma_{j}^{\prime}}\right))\\}$
$\displaystyle\leq\max_{0\leq j\leq
l}\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(\frac{1}{2}}\right)\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(\sigma_{j}^{\prime}}\right)}\right\\},\text{
by Proposition~{}\ref{prop:radius} as
}\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(\sigma_{j}^{\prime}}\right)<2\rho({\mathcal{G}})$
$\displaystyle=\frac{1}{2}\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(\sigma_{l}^{\prime}}\right)$
$\displaystyle<\frac{2\beta}{3},\text{ from (\ref{eqn:sigma})}.$

So, $\widetilde{g}(\tau_{l})$ is a simplex of
$\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})$. This implies that
$\widetilde{g}$ is a simplicial map.

We invoke Proposition 2.2 to show that the diagram commutes up to homotopy. We
need to argue that the simplicial maps $g$ and $\phi\circ\widetilde{g}$
satisfy the conditions of Proposition 2.2:

  1. (a)

For any vertex $v\in{\mathcal{K}}$,

$(\phi\circ\widetilde{g})(v)=\phi(\theta\mathopen{}\mathclose{{}\left(g(v)^{\prime}}\right))=\phi(g(v)^{\prime})=g(v).$

  2. (b)

For any simplex $\sigma=[a_{0},a_{1},\ldots,a_{k}]$ of ${\mathcal{K}}$, we
have for $0\leq i\leq k$

$\displaystyle d_{S}(g(a_{i}),(\phi\circ\widetilde{g})(\widehat{\sigma}))$
$\displaystyle=d_{S}(g(a_{i}),\phi(\theta\mathopen{}\mathclose{{}\left(\sigma^{\prime}}\right)))$
$\displaystyle=d_{\mathcal{G}}\mathopen{}\mathclose{{}\left(a_{i}^{\prime},\theta\mathopen{}\mathclose{{}\left(\sigma^{\prime}}\right)}\right)+\frac{\beta}{3},\text{
since }(a_{i}^{\prime},g(a_{i}))\in\mathcal{C}$
$\displaystyle\leq\frac{1}{2}\mathrm{diam}_{{\mathcal{G}}}\mathopen{}\mathclose{{}\left(\sigma^{\prime}}\right)+\frac{\beta}{3},\text{
by Proposition~{}\ref{prop:radius} as
}\theta\mathopen{}\mathclose{{}\left(a_{i}^{\prime}}\right)=a_{i}^{\prime}$
$\displaystyle=\frac{2\beta}{3}+\frac{\beta}{3},\text{ from
(\ref{eqn:sigma})}$ $\displaystyle=\beta.$

So, $g(\sigma)\cup(\phi\circ\widetilde{g})(\widehat{\sigma})$ is a simplex of
$\mathcal{R}_{\beta}(S)$.

Therefore, Proposition 2.2 implies that the diagram commutes. Since
$\big{\lvert}{\mathcal{K}}\big{\rvert}={\mathbb{S}}^{k}$ and $g$ is arbitrary,
we conclude that $\big{\lvert}\phi\big{\rvert}$ induces a surjective
homomorphism. ∎

######  Theorem 3.8 (Homotopy Equivalence under Gromov-Hausdorff Distance).

Let $({\mathcal{G}},d_{\mathcal{G}})$ be a compact, path-connected metric
graph, $(S,d_{S})$ a metric space, and $\beta>0$ a number such that

$3d_{GH}({\mathcal{G}},S)<\beta<\frac{3\rho({\mathcal{G}})}{4}.$

Then, $\big{\lvert}\mathcal{R}_{\beta}(S)\big{\rvert}\simeq{\mathcal{G}}$.

###### Proof.

By Lemma 3.6 and Lemma 3.7, for any $k\geq 0$

$\big{\lvert}\phi\big{\rvert}_{*}:\pi_{k}\mathopen{}\mathclose{{}\left(\big{\lvert}\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\big{\rvert}}\right)\xrightarrow{\quad\quad}\pi_{k}\mathopen{}\mathclose{{}\left(\big{\lvert}\mathcal{R}_{\beta}(S)\big{\rvert}}\right).$

is an isomorphism, where the simplicial map is defined in (2). By the
Whitehead’s theorem, we have that $\big{\lvert}\phi\big{\rvert}$ is a homotopy
equivalence. On the other hand, since $\frac{2\beta}{3}<\rho({\mathcal{G}})$,
Theorem 2.5 implies that
$\big{\lvert}\mathcal{R}_{\frac{2\beta}{3}}({\mathcal{G}})\big{\rvert}$ is
homotopy equivalent to ${\mathcal{G}}$. Therefore, we conclude that
$\big{\lvert}\mathcal{R}_{\beta}(S)\big{\rvert}\simeq{\mathcal{G}}$. ∎

##  4\. Embedded Metric Graphs

This section considers the Vietoris–Rips complexes of a Euclidean subset $S$
near (in the Hausdorff distance) to an embedded metric graph ${\mathcal{G}}$.
We first define an embedded metric graph. For a (continuous) path
$\gamma:[0,1]\to{\mathbb{R}}^{d}$, we denote by $L_{{\mathbb{R}}^{d}}(\gamma)$
its usual Euclidean length222For details on the definition of this length, see
[7, Definition 2.3.1] for example.. The path $\gamma$ is called _rectifiable_
if $L_{{\mathbb{R}}^{d}}(\gamma)$ is finite. Using this length structure, a
Euclidean subset $X\subset{\mathbb{R}}^{d}$ can be endowed with yet another
metric $d_{l}$, sometimes called the _length metric_ , defined by

$d_{l}(a,b)\stackrel{{\scriptstyle
def}}{{=}}\inf_{\begin{subarray}{c}\gamma:[0,1]\to X\\\
\gamma(0)=a,\gamma(1)=b\end{subarray}}L_{{\mathbb{R}}^{d}}(\gamma),$

where the infimum is taken over all continuous path $\gamma$ (contained in
$X$) joining $a$ and $b$.

######  Definition 4.1 (Embedded Metric Graph).

A subset ${\mathcal{G}}\subset{\mathbb{R}}^{d}$ is called an _embedded metric
graph_ if the length metric turns $({\mathcal{G}},d_{l})$ into a metric graph
(Definition 2.3).

If ${\mathcal{G}}$ is an embedded metric graph, then we denote its length
metric by $d_{\mathcal{G}}$ to retain uniformity with the rest of the paper.
We always assume that ${\mathcal{G}}$ is path-connected and it has finitely
many vertices. We remark that the topologies on ${\mathcal{G}}$ induced by the
standard Euclidean norm
$\mathopen{}\mathclose{{}\left\lVert\cdot}\right\rVert$ and $d_{\mathcal{G}}$
are not always the same. However, the two metrics are equivalent when the
distortion of embedding of ${\mathcal{G}}$ is finite.

######  Definition 4.2 (Distortion of Embedding).

The _distortion of embedding_ of a metric graph
${\mathcal{G}}\subset{\mathbb{R}}^{d}$, denoted $\delta({\mathcal{G}})$, is
defined by

$\delta({\mathcal{G}})\stackrel{{\scriptstyle
def}}{{=}}\sup_{\begin{subarray}{c}a,b\in{\mathcal{G}}\\\ a\neq
b\end{subarray}}\frac{d_{\mathcal{G}}(a,b)}{\mathopen{}\mathclose{{}\left\lVert
a-b}\right\rVert}$

The distortion $\delta({\mathcal{G}})$ is a number greater than $1$, unless
${\mathcal{G}}$ is a straight line segment. On the other extreme,
$\delta({\mathcal{G}})$ can become infinity; take
${\mathcal{G}}=\\{(x,y)\in{\mathbb{R}}^{2}\mid x^{2}=y^{3}\\}$ for example.
Throughout this paper, we always assume that the embedded metric graph
${\mathcal{G}}$ has a finite distortion of embedding. Then, for any two points
$a,b\in{\mathcal{G}}$, we have

$\mathopen{}\mathclose{{}\left\lVert a-b}\right\rVert\leq
d_{\mathcal{G}}(a,b)\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left\lVert
a-b}\right\rVert.$

As a consequence, the two metrics
$\mathopen{}\mathclose{{}\left\lVert\cdot}\right\rVert$ and $d_{\mathcal{G}}$
on ${\mathcal{G}}$ are equivalent.

In this section, we consider a subset $S\subset{\mathbb{R}}^{d}$ that is close
to an embedded metric graph ${\mathcal{G}}$ in the Hausdorff distance. As
shown for abstract metric graphs (Theorem 3.8), we wonder if the (Euclidean)
Vietoris–Rips complex of $S$ can also recover an embedded metric graph
${\mathcal{G}}$. To our disappointment, we find that however small the
Hausdorff distance $d_{H}(S,{\mathcal{G}})$ be, the Euclidean Vietoris–Rips
complex of $S$ is not generally homotopy equivalent to ${\mathcal{G}}$. As a
remedy, we consider the Vietoris–Rips of $S$ under a parametric family of
metrics, we call it the $\varepsilon$–metric $(d^{\varepsilon})$. The idea is
to first consider the Euclidean Vietoris–Rips complex of $S$ for a small scale
$\varepsilon>0$, then the shortest path distance in its $1$–skeleton defines
the $d^{\varepsilon}$ metric on $S$. The metric $d^{\varepsilon}$ is
computable from the pairwise Euclidean pairwise distances of points in $S$.

In Subsection 4.1, we formally define this metric and explore some useful
properties thereof. We then define in Subsection 4.2 a variant of the concept
of a circumcenter in the context of $(S,d^{\varepsilon})$. Finally, Subsection
4.3 presents the main homotopy equivalence result for embedded metric graphs.

###  4.1. Path Metric

A (non-empty) subset $S\subset{\mathbb{R}}^{d}$ comes equipped with the
standard Euclidean metric, given by the Euclidean norm
$\mathopen{}\mathclose{{}\left\lVert\cdot}\right\rVert$. We define another
metric, denoted $d^{\varepsilon}$, using the pairwise Euclidean distances of
points in $S$. For a positive number $\varepsilon$, we first introduce the
notion of an $\varepsilon$–path.

######  Definition 4.3 ($\varepsilon$–Path).

Let $S\subset{\mathbb{R}}^{d}$ be non-empty and $\varepsilon>0$ a number. For
$a,b\in S$, an _$\varepsilon$ –path_ from $a$ to $b$, denoted by
$\mathcal{P}^{\varepsilon}$, is a finite sequence
$\\{y_{i}\\}_{i=0}^{k+1}\subset S$ such that $y_{0}=a$, $y_{k+1}=b$, and
$\mathopen{}\mathclose{{}\left\lVert y_{i}-y_{i+1}}\right\rVert<\varepsilon$
for all $i=0,1,\ldots,k$.

The length of $\mathcal{P}^{\varepsilon}$ is defined by

$L(\mathcal{P}^{\varepsilon})\stackrel{{\scriptstyle
def}}{{=}}\sum_{i=0}^{k}\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert.$

Now, we are in a position to define the path metric $d^{\varepsilon}$ on $S$.

######  Definition 4.4 ($d^{\varepsilon}$–Metric).

Let $S\subset{\mathbb{R}}^{d}$ be non-empty and $\varepsilon>0$ a number. The
$\varepsilon$–metric, denoted $d^{\varepsilon}$, between any $a,b\in S$ is
defined by

$d^{\varepsilon}(a,b)\stackrel{{\scriptstyle
def}}{{=}}\inf_{\mathcal{P}^{\varepsilon}}L(\mathcal{P}^{\varepsilon}),$

where the infimum is taken over all $\varepsilon$–paths
$\mathcal{P}^{\varepsilon}$ from $a$ to $b$.

The metric $d^{\varepsilon}$ is not finite, in general, for all
$\varepsilon>0$. When $d^{\varepsilon}$ is finite, however,
$(S,d^{\varepsilon})$ qualifies to be a metric space. In this metric, we
denote the diameter of a subset $Y\subset S$ by
$\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(Y}\right)$. For any
scale $\beta>0$, the Vietoris–Rips complex of $(S,d^{\varepsilon})$ is denoted
by $\mathcal{R}^{\varepsilon}_{\beta}(S)$. For any two points $a,b\in S$, we
now compare $d^{\varepsilon}(a,b)$ to their standard Euclidean distance
$\mathopen{}\mathclose{{}\left\lVert a-b}\right\rVert$.

######  Proposition 4.5.

Let $\varepsilon>0$ be a number and $S\subset{\mathbb{R}}^{d}$ non-empty. For
any pair of points $a,b\in S$, we have

$\mathopen{}\mathclose{{}\left\lVert a-b}\right\rVert\leq
d^{\varepsilon}(a,b),$

provided $d^{\varepsilon}(a,b)$ is finite.

###### Proof.

By Definition 4.4, for any $\eta>0$, there exists an $\varepsilon$–path
$\mathcal{P}^{\varepsilon}=\\{y_{i}\\}_{i=0}^{k+1}$ from $a$ to $b$ such that

$\displaystyle d^{\varepsilon}(a,b)+\eta$
$\displaystyle\geq\sum_{i=0}^{k}\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert$
$\displaystyle\geq\mathopen{}\mathclose{{}\left\lVert
y_{0}-y_{k+1}}\right\rVert,\text{ by the triangle inequality}$
$\displaystyle=\mathopen{}\mathclose{{}\left\lVert a-b}\right\rVert.$

This holds for any arbitrary $\eta>0$, consequently
$d^{\varepsilon}(a,b)\geq\mathopen{}\mathclose{{}\left\lVert
a-b}\right\rVert$. ∎

The metric space $(S,d^{\varepsilon})$ manifests some nice metric properties
when the subset $S\subset{\mathbb{R}}^{d}$ is in a close Hausdorff–proximity
to an embedded metric graph ${\mathcal{G}}$. As the following proposition
shows, a geodesic of ${\mathcal{G}}$ can be approximated by an
$\varepsilon$–path, with a reasonable bound on its length. A particular bound
has already been found in [12]. We provide here a more general
result—additionally demonstrating that such as approximation can be made as
accurate as needed by adjusting the Hausdorff distance between ${\mathcal{G}}$
and $S$.

######  Proposition 4.6 (Approximation of Geodesics by $\varepsilon$–Paths).

Let ${\mathcal{G}}\subset{\mathbb{R}}^{d}$ be an embedded metric graph and
$S\subset{\mathbb{R}}^{d}$ such that
$d_{H}({\mathcal{G}},S)<\frac{1}{2}\xi\varepsilon$ for some $\xi\in(0,1)$ and
$\varepsilon>0$. For any $a,b\in{\mathcal{G}}$ and corresponding
$a^{\prime},b^{\prime}\in S$ with $\mathopen{}\mathclose{{}\left\lVert
a-a^{\prime}}\right\rVert,\mathopen{}\mathclose{{}\left\lVert
b-b^{\prime}}\right\rVert<\frac{1}{2}\xi\varepsilon$, there exists an
$\varepsilon$–path $\mathcal{P}^{\varepsilon}$ from $a^{\prime}$ to
$b^{\prime}$ such that

$(1-\xi)L(\mathcal{P}^{\varepsilon})\leq d_{\mathcal{G}}(a,b)+\xi\varepsilon.$

In particular, $L(\mathcal{P}^{\varepsilon})\leq
2d_{\mathcal{G}}(a,b)+\varepsilon$ when $\xi\leq\frac{1}{2}$.

###### Proof.

Let $\gamma:[0,1]\to{\mathcal{G}}$ be a shortest path on ${\mathcal{G}}$
joining $a$ and $b$. We can find a partition

$0=t_{0}<t_{1}<\ldots<t_{k}<t_{k+1}=b$

of $[0,1]$ such that

(5)
$L\mathopen{}\mathclose{{}\left(\gamma\big{|}_{[t_{i},t_{i+1}]}}\right)=(1-\xi)\varepsilon\text{
for }i=0,1,\ldots,k-1,$

and
$L\mathopen{}\mathclose{{}\left(\gamma\big{|}_{[t_{k},t_{k+1}]}}\right)\leq(1-\xi)\varepsilon$.

Note that $k$ could also be $0$ if $L(\gamma)<(1-\xi)\varepsilon$. In order to
construct a $\varepsilon$–path
$\mathcal{P}^{\varepsilon}=\\{y_{i}\\}_{i=0}^{k+1}$, we first set
$y_{0}=a^{\prime}$ and $y_{k+1}=b^{\prime}$. For $i\in\\{1,2,\ldots,k\\}$,
choose $y_{i}\in S$ such that
$\mathopen{}\mathclose{{}\left\lVert\gamma(t_{i})-y_{i}}\right\rVert<\frac{1}{2}\xi\varepsilon$.
Since $\gamma(t_{0})=a$ and $\gamma(t_{k+1})=b$, we have that

$\mathopen{}\mathclose{{}\left\lVert\gamma(t_{i})-y_{i}}\right\rVert<\frac{1}{2}\xi\varepsilon\text{
for all }i=0,1,\ldots,k+1.$

We first show that $\mathcal{P}^{\varepsilon}$ is, in fact, an
$\varepsilon$–path. For each $i=0,1,\ldots,k$, from the triangle inequality we
get

$\displaystyle\mathopen{}\mathclose{{}\left\lVert y_{i}-y_{i+1}}\right\rVert$
$\displaystyle\leq\mathopen{}\mathclose{{}\left\lVert
y_{i}-\gamma(t_{i})}\right\rVert+\mathopen{}\mathclose{{}\left\lVert\gamma(t_{i})-\gamma(t_{i+1})}\right\rVert+\mathopen{}\mathclose{{}\left\lVert\gamma(t_{i+1})-y_{i+1}}\right\rVert$
$\displaystyle<\frac{1}{2}\xi\varepsilon+\mathopen{}\mathclose{{}\left\lVert\gamma(t_{i})-\gamma(t_{i+1})}\right\rVert+\frac{1}{2}\xi\varepsilon$
$\displaystyle\leq
d_{\mathcal{G}}(\gamma(t_{i}),\gamma(t_{i+1}))+\xi\varepsilon$
$\displaystyle=L\mathopen{}\mathclose{{}\left(\gamma\big{|}_{[t_{i},t_{i+1}]}}\right)+\xi\varepsilon,\text{
since }\gamma\text{ is a geodesic}$
$\displaystyle\leq(1-\xi)\varepsilon+\xi\varepsilon,\text{ by
(\ref{eqn:gamma})}$ $\displaystyle=\varepsilon.$

Finally,

$\displaystyle d_{\mathcal{G}}(a,b)$
$\displaystyle=\sum_{i=0}^{k}L\mathopen{}\mathclose{{}\left(\gamma\big{|}_{[t_{i},t_{i+1}]}}\right)$
$\displaystyle=\sum_{i=0}^{k-1}d_{\mathcal{G}}(\gamma(t_{i}),\gamma(t_{i+1}))+d_{\mathcal{G}}(\gamma(t_{k}),\gamma(t_{k+1}))$
$\displaystyle=\sum_{i=0}^{k-1}(1-\xi)\varepsilon+d_{\mathcal{G}}(\gamma(t_{k}),\gamma(t_{k+1}))\text{,
from (\ref{eqn:gamma})}$
$\displaystyle>(1-\xi)\sum_{i=0}^{k-1}\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert+d_{\mathcal{G}}(\gamma(t_{k}),\gamma(t_{k+1})),\text{
as already proved }\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert>\varepsilon$
$\displaystyle\geq(1-\xi)\sum_{i=0}^{k-1}\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert+\mathopen{}\mathclose{{}\left\lVert\gamma(t_{k})-\gamma(t_{k+1})}\right\rVert$
$\displaystyle>(1-\xi)\sum_{i=0}^{k-1}\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert+\mathopen{}\mathclose{{}\left\lVert
y_{k}-y_{k+1}}\right\rVert-\xi\varepsilon,\text{ since
}\mathopen{}\mathclose{{}\left\lVert\gamma(t_{i})-y_{i}}\right\rVert<\frac{1}{2}\xi\varepsilon$
$\displaystyle\geq(1-\xi)\sum_{i=0}^{k-1}\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert+(1-\xi)\mathopen{}\mathclose{{}\left\lVert
y_{k}-y_{k+1}}\right\rVert-\xi\varepsilon,\text{ since }0<\xi<1$
$\displaystyle=(1-\xi)\sum_{i=0}^{k}\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert-\xi\varepsilon$
$\displaystyle=(1-\xi)L(\mathcal{P}^{\varepsilon})-\xi\varepsilon.$

This completes the proof. ∎

The approximation of geodesics of ${\mathcal{G}}$ by the $\varepsilon$–path
facilitates the comparison of the $d^{\varepsilon}$ metric and the geodesic
metric $d_{\mathcal{G}}$ as presented in the following proposition.

######  Proposition 4.7 (Comparing Distances).

Let ${\mathcal{G}}\subset{\mathbb{R}}^{d}$ be an embedded graph, and let
$S\subset{\mathbb{R}}^{d}$ and $\varepsilon>0$ be such that
$d_{H}({\mathcal{G}},S)<\frac{1}{4}\varepsilon$. For any $a,b\in{\mathcal{G}}$
and corresponding $a^{\prime},b^{\prime}\in S$ with
$\mathopen{}\mathclose{{}\left\lVert
a-a^{\prime}}\right\rVert,\mathopen{}\mathclose{{}\left\lVert
b-b^{\prime}}\right\rVert<\frac{1}{4}\varepsilon$, we have

(6)
$\frac{1}{\delta({\mathcal{G}})}d_{\mathcal{G}}(a,b)-\frac{\varepsilon}{2}\leq
d^{\varepsilon}(a^{\prime},b^{\prime})\leq 2d_{\mathcal{G}}(a,b)+\varepsilon.$

###### Proof.

(a) We have

$\displaystyle d_{\mathcal{G}}(a,b)$
$\displaystyle\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left\lVert
a-b}\right\rVert,\text{ from definition of the distortion of embedding}$
$\displaystyle\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lVert
a-a^{\prime}}\right\rVert+\mathopen{}\mathclose{{}\left\lVert
a^{\prime}-b^{\prime}}\right\rVert+\mathopen{}\mathclose{{}\left\lVert
b^{\prime}-b}\right\rVert}\right)$
$\displaystyle\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lVert
a^{\prime}-b^{\prime}}\right\rVert+\frac{\varepsilon}{2}}\right)$
$\displaystyle\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(d^{\varepsilon}(a^{\prime},b^{\prime})+\frac{\varepsilon}{2}}\right),\text{
by Proposition~{}\ref{prop:s-eps}}.$

So, the first inequality holds.

(b) For the second inequality, we apply Proposition 4.6 on the pairs of points
$a,b\in{\mathcal{G}}$ and $a^{\prime},b^{\prime}\in S$, to get an
$\varepsilon$–path $\mathcal{P}^{\varepsilon}$ from $a^{\prime}$ to
$b^{\prime}$ with $L(\mathcal{P}^{\varepsilon})\leq
2d_{\mathcal{G}}(a^{\prime},b^{\prime})+\varepsilon$. By Definition 4.4, on
the other hand, $d^{\varepsilon}(a^{\prime},b^{\prime})\leq
L(\mathcal{P}^{\varepsilon})$. Together they imply

$d^{\varepsilon}(a^{\prime},b^{\prime})\leq
2d_{\mathcal{G}}(a,b)+\varepsilon.$

∎

We conclude our discussion on the $d^{\varepsilon}$ metric with the
observation that an $\varepsilon$–path has to lie close to the geodesics of
${\mathcal{G}}$—provided its length is bounded in terms of the convexity
radius and distortion of embedding of ${\mathcal{G}}$. We make this idea
concise in the following proposition.

######  Proposition 4.8 (Approximation of $\varepsilon$–Paths by Geodesics).

Let ${\mathcal{G}}\subset{\mathbb{R}}^{d}$ be an embedded metric graph and
$S\subset{\mathbb{R}}^{d}$ be such that
$4d_{H}({\mathcal{G}},S)<\varepsilon<\frac{2\rho({\mathcal{G}})}{\delta({\mathcal{G}})}$
for some $\varepsilon>0$. Let $\mathcal{P}^{\varepsilon}$ be an
$\varepsilon$–path from $a\in S$ to $b\in S$ with
$\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left[L(\mathcal{P}^{\varepsilon})+\frac{\varepsilon}{2}}\right]<\rho({\mathcal{G}})$.
If $x^{\prime}\in{\mathcal{G}}$ on the geodesic joining
$a^{\prime},b^{\prime}\in{\mathcal{G}}$ with
$\mathopen{}\mathclose{{}\left\lVert
a-a^{\prime}}\right\rVert,\mathopen{}\mathclose{{}\left\lVert
b-b^{\prime}}\right\rVert<\frac{\varepsilon}{4}$, then there exists
$y\in\mathcal{P}^{\varepsilon}$ such that
$d^{\varepsilon}(x,y)<\frac{1}{2}\mathopen{}\mathclose{{}\left[3\delta({\mathcal{G}})+2}\right]\varepsilon$
for any $x\in S$ with $\mathopen{}\mathclose{{}\left\lVert
x-x^{\prime}}\right\rVert<\frac{\varepsilon}{4}$.

###### Proof.

We first note from Proposition 4.7 that

$d_{\mathcal{G}}(a^{\prime},b^{\prime})\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(d^{\varepsilon}(a,b)+\frac{\varepsilon}{2}}\right)\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(L(\mathcal{P}^{\varepsilon})+\frac{\varepsilon}{2}}\right)<\rho({\mathcal{G}}).$

So, there exists a unique shortest path, say $\gamma$, joining $a^{\prime}$
and $b^{\prime}$. Moreover, there exists a vertex $v$ of ${\mathcal{G}}$ such
that $\gamma\subset\textbf{st}(v)$. We now let
$\mathcal{P}^{\varepsilon}=\\{y_{i}\\}_{i=0}^{k+1}\subset S$.

Since $d_{H}({\mathcal{G}},S)<\frac{\varepsilon}{4}$, there exists a
corresponding sequence $\\{y_{i}^{\prime}\\}_{i=0}^{k+1}\subset{\mathcal{G}}$
such that $y_{0}^{\prime}=a^{\prime}$ and $y_{k+1}^{\prime}=b^{\prime}$, and
$\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i}^{\prime}}\right\rVert<\frac{\varepsilon}{4}$ for all $0\leq i\leq
k$. So, we have

$d_{\mathcal{G}}(y_{i}^{\prime},y_{i+1}^{\prime})\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left\lVert
y_{i}^{\prime}-y_{i+1}^{\prime}}\right\rVert\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert+\frac{\varepsilon}{2}}\right)\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(L(\mathcal{P}^{\varepsilon})+\frac{\varepsilon}{2}}\right)<\rho({\mathcal{G}}).$

Consequently, for each $0\leq i\leq k$, there exists a unique geodesic in
${\mathcal{G}}$ joining $y_{i}^{\prime}$ and $y_{i+1}^{\prime}$; call it
$\widetilde{\gamma}_{i}$. Concatenating them, we get a (continuous) path
$\widetilde{\gamma}:[0,1]\to{\mathcal{G}}$ joining $a^{\prime}$ and
$b^{\prime}$ and a partition

$0=t_{0}<t_{1}<\ldots<t_{k}<t_{k+1}=1$

of $[0,1]$ such that
$\widetilde{\gamma}([t_{i},t_{i+1}])=\widetilde{\gamma}_{i}$ for $0\leq i\leq
k$.

We now argue that $\gamma\subset\widetilde{\gamma}$. Let us assume the
contrary. We note that both $\gamma$ and $\widetilde{\gamma}$ are continuous
paths on ${\mathcal{G}}$ joining the same endpoints—$a^{\prime}$ and
$b^{\prime}$. The only way $\widetilde{\gamma}$ fails to cover $\gamma$ if
there exists a vertex $w$ of ${\mathcal{G}}$ such that
$w\in\widetilde{\gamma}$ and $w\neq v$, i.e., $L(\widetilde{\gamma})\geq
2\rho({\mathcal{G}})$. Without any loss of generality, then there must exist
$0\leq m\leq k$ such that
$d_{\mathcal{G}}(y_{m}^{\prime},b^{\prime})\geq\rho({\mathcal{G}})$. As a
result,

$\displaystyle L(\mathcal{P}^{\varepsilon})$
$\displaystyle\geq\sum_{i=m}^{k}\mathopen{}\mathclose{{}\left\lVert
y_{i}-y_{i+1}}\right\rVert$
$\displaystyle\geq\mathopen{}\mathclose{{}\left\lVert
y_{m}-y_{k+1}}\right\rVert\text{, by the triangle inequality}$
$\displaystyle\geq\mathopen{}\mathclose{{}\left\lVert
y_{m}^{\prime}-b^{\prime}}\right\rVert-\frac{\varepsilon}{2}$
$\displaystyle\geq\frac{1}{\delta({\mathcal{G}})}d_{\mathcal{G}}(y_{m}^{\prime},b^{\prime})-\frac{\varepsilon}{2}$
$\displaystyle\geq\frac{\rho({\mathcal{G}})}{\delta({\mathcal{G}})}-\frac{\varepsilon}{2}.$

This is a contradiction. So, $\gamma\subset\widetilde{\gamma}$. Therefore,
$x^{\prime}$ belongs to $\widetilde{\gamma}$. By the construction of
$\widetilde{\gamma}$, there exists $0\leq l\leq k$ such that
$x^{\prime}\in\widetilde{\gamma}_{l}$. Without any loss of generality, let’s
assume that
$d_{\mathcal{G}}(y_{l}^{\prime},x^{\prime})\leq\frac{1}{2}d_{\mathcal{G}}(y_{l}^{\prime},y_{l+1}^{\prime})$.
Then by Proposition 4.7,

$d_{\mathcal{G}}(y_{l}^{\prime},y_{l+1}^{\prime})\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(d^{\varepsilon}(y_{l},y_{l+1})+\frac{\varepsilon}{2}}\right)<\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\varepsilon+\frac{\varepsilon}{2}}\right)\leq\frac{3}{2}\delta({\mathcal{G}})\varepsilon.$

We set $y=y_{l}\in\mathcal{P}^{\varepsilon}$, and note from Proposition 4.7,
we get

$d^{\varepsilon}(x,y)=d^{\varepsilon}(x,y_{l})\leq
2d_{\mathcal{G}}(x^{\prime},y_{l}^{\prime})+\varepsilon\leq
2\times\frac{1}{2}d_{\mathcal{G}}(y_{l}^{\prime},y_{l+1}^{\prime})+\varepsilon<\frac{1}{2}\mathopen{}\mathclose{{}\left[3\delta({\mathcal{G}})+2}\right]\varepsilon.$

∎

###  4.2. $\alpha$–Circumcenter

As observed in Subsection 3.1, _small_ subsets of ${\mathcal{G}}$ have a
unique circumcenter. The same can not always be ascertained for _small_
subsets of the metric space $(S,d^{\varepsilon})$. We introduce the notion of
an $\alpha$–circumcenter so that properties similar to Proposition 3.2 and
Proposition 3.3 still hold for the subsets of $(S,d^{\varepsilon})$. We now
define it for a general metric space. The inspiration stems from the property
of a circumcenter as demonstrated in Proposition 3.2.

######  Definition 4.9 ($\alpha$–Circumcenter).

Let $Y$ be a subset of a metric space $(X,d_{X})$ and $\alpha\geq 0$ a number.
A point $x\in X$ is called an $\alpha$–circumcenter of $Y$, denoted
$\theta_{\alpha}\mathopen{}\mathclose{{}\left(Y}\right)$, if $Y$ is contained
in the closed (metric) ball around $x$ of radius
$\frac{1}{2}\mathrm{diam}_{X}\mathopen{}\mathclose{{}\left(Y}\right)+\alpha$.

When $Y$ contains just a single point, we define

$\theta_{\alpha}\mathopen{}\mathclose{{}\left(\\{v\\}}\right)\stackrel{{\scriptstyle
def}}{{=}}v$

for any $\alpha$. We also remark that
$\theta_{\alpha}\mathopen{}\mathclose{{}\left(Y}\right)$ of a subset $Y$ may
not always exist in a metric space for a given $\alpha$. However, a uniform
$\alpha$ can always be chosen so that
$\theta_{\alpha}\mathopen{}\mathclose{{}\left(Y}\right)$ exists for certain
subsets $Y$ of the metric space $(S,d^{\varepsilon})$.

######  Proposition 4.10 ($\alpha$–Circumcenter).

Let ${\mathcal{G}}\subset{\mathbb{R}}^{d}$ be an embedded metric graph. Let
$S\subset{\mathbb{R}}^{d}$ and $\varepsilon>0$ be such that
$4d_{H}({\mathcal{G}},S)<\varepsilon<\frac{2\rho({\mathcal{G}})}{\delta({\mathcal{G}})}$.
For any compact $Y\subset S$ with
$\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left[\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(Y}\right)+\frac{\varepsilon}{2}}\right]<\rho({\mathcal{G}})$,
an $\alpha$–circumcenter
$\theta_{\alpha}\mathopen{}\mathclose{{}\left(Y}\right)$ of $Y$ exists for
$\alpha=[9\delta({\mathcal{G}})+8]\varepsilon$.

###### Proof.

Since $Y$ is compact, there exist $a,b\in Y$ such that
$\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(Y}\right)=d^{\varepsilon}(a,b)$.
Let $\eta>0$ be arbitrary. Then there exists an $\varepsilon$–path
$\mathcal{P}^{\varepsilon}$ from $a$ to $b$ such that
$L(\mathcal{P}^{\varepsilon})\leq d^{\varepsilon}(a,b)+\eta$. Let $\theta\in
S$ be a point on $\mathcal{P}^{\varepsilon}$ such that

$d^{\varepsilon}(a,\theta)+\eta\geq\frac{1}{2}L(\mathcal{P}^{\varepsilon})-\varepsilon,\text{
and
}d^{\varepsilon}(\theta,b)+\eta\geq\frac{1}{2}L(\mathcal{P}^{\varepsilon})-\varepsilon.$

Since $L(\mathcal{P}^{\varepsilon})\geq d^{\varepsilon}(a,b)$,

(7)
$d^{\varepsilon}(a,\theta)+\eta\geq\frac{1}{2}d^{\varepsilon}(a,b)-\varepsilon,\text{
and
}d^{\varepsilon}(\theta,b)+\eta\geq\frac{1}{2}d^{\varepsilon}(a,b)-\varepsilon.$

$w$$a$$d$$\theta$$b$$a_{1}$$d_{1}$$\theta_{1}$$b_{1}$$d_{2}$$a^{\prime}$$b^{\prime}$$a_{1}^{\prime}$$b_{1}^{\prime}$
Figure 2. The star of the vertex $w$ of the metric graph ${\mathcal{G}}$ is
shown. The $\varepsilon$–paths $\mathcal{P}^{\varepsilon}_{1}$ and
$\mathcal{P}^{\varepsilon}_{2}$ are shown in red and blue, respectively.

Similarly for $Y_{1}$, there exist points $a_{1},b_{1},\theta_{1}\in Y_{1}$
such that
$\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(Y_{1}}\right)=d^{\varepsilon}(a_{1},b_{1})$,
and

(8)
$d^{\varepsilon}(a_{1},\theta_{1})+\eta\geq\frac{1}{2}d^{\varepsilon}(a_{1},b_{1})-\varepsilon,\text{
and
}d^{\varepsilon}(\theta_{1},b_{1})+\eta\geq\frac{1}{2}d^{\varepsilon}(a_{1},b_{1})-\varepsilon.$

Since $d_{H}({\mathcal{G}},S)<\frac{\varepsilon}{4}$, there exist
corresponding points
$a^{\prime},b^{\prime},a_{1}^{\prime},b_{1}^{\prime}\in{\mathcal{G}}$ such
that $\mathopen{}\mathclose{{}\left\lVert
a-a^{\prime}}\right\rVert<\frac{\varepsilon}{4}$,
$\mathopen{}\mathclose{{}\left\lVert
b-b^{\prime}}\right\rVert<\frac{\varepsilon}{4}$,
$\mathopen{}\mathclose{{}\left\lVert
a_{1}-a_{1}^{\prime}}\right\rVert<\frac{\varepsilon}{4}$, and
$\mathopen{}\mathclose{{}\left\lVert
b_{1}-b_{1}^{\prime}}\right\rVert<\frac{\varepsilon}{4}$. See Figure 2.

By Proposition 4.7, get

$d_{\mathcal{G}}(a^{\prime},b^{\prime})\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(d^{\varepsilon}(a,b)+\frac{\varepsilon}{2}}\right)\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(Y}\right)+\frac{\varepsilon}{2}}\right)<\rho({\mathcal{G}}).$

Similarly
$d_{\mathcal{G}}(a_{1}^{\prime},b_{1}^{\prime})<\rho({\mathcal{G}})$. So,
$a^{\prime},b^{\prime},a_{1}^{\prime},b_{1}\in\textbf{st}(w)$ for some vertex
$w$ of ${\mathcal{G}}$. For the proof, we consider the most extreme case, when
all of them lie on two different edges of ${\mathcal{G}}$ incident to $w$. Let
$v\in S$ such that $\mathopen{}\mathclose{{}\left\lVert
v-w}\right\rVert<\frac{\varepsilon}{4}$. Since $w$ lies on the geodesic
joining $a,b$, Proposition 4.8 implies that there exists $d\in S$ on
$\mathcal{P}^{\varepsilon}$ such that
$d^{\varepsilon}(v,d)\leq\frac{1}{2}[3\delta({\mathcal{G}})+2]\varepsilon$.
Similarly, there exists $d_{1}\in S$ on $\mathcal{P}^{\varepsilon}_{1}$ such
that
$d^{\varepsilon}(v,d_{1})\leq\frac{1}{2}[3\delta({\mathcal{G}})+2]\varepsilon$.
Without any loss of generality, we assume that $\theta$ lies between $d,b$ on
$\mathcal{P}^{\varepsilon}$ and $\theta_{1}$ lies between $d_{1},b_{1}$ on
$\mathcal{P}^{\varepsilon}_{1}$. Also, there exists an $\varepsilon$–path
$\mathcal{P}^{\varepsilon}_{2}$ from $b$ to $b_{1}$ such that
$L(\mathcal{P}^{\varepsilon}_{2})\leq d^{\varepsilon}(b,b_{1})+\eta$. By
Proposition 4.8, there exists $d_{2}\in S$ on $\mathcal{P}^{\varepsilon}_{2}$
such that
$d^{\varepsilon}(v,d_{2})\leq\frac{1}{2}[3\delta({\mathcal{G}})+2]\varepsilon$.
From the triangle inequality, we get

$d^{\varepsilon}(d,d_{i})\leq[3\delta({\mathcal{G}})+2]\varepsilon\text{ for
}i=1,2,\text{ and
}d^{\varepsilon}(d_{1},d_{2})\leq[3\delta({\mathcal{G}})+2]\varepsilon.$

Now,

$\displaystyle d^{\varepsilon}(b,b_{1})+\eta$ $\displaystyle\geq
d^{\varepsilon}(b,d_{2})+d^{\varepsilon}(d_{2},b_{1})$
$\displaystyle\geq[d^{\varepsilon}(b,d)-d^{\varepsilon}(d_{2},d)]+[d^{\varepsilon}(b_{1},d_{1})-d^{\varepsilon}(d_{1},d_{2})],\text{
by the triangle inequality}$
$\displaystyle=d^{\varepsilon}(b,d)+d^{\varepsilon}(b_{1},d_{1})-d^{\varepsilon}(d,d_{2})-d^{\varepsilon}(d_{1},d_{2})$
$\displaystyle=[d^{\varepsilon}(b,d)+\eta]+[d^{\varepsilon}(b_{1},d_{1})+\eta]-d^{\varepsilon}(d,d_{2})-d^{\varepsilon}(d_{1},d_{2})-2\eta$
$\displaystyle\geq[d^{\varepsilon}(b,\theta)+d^{\varepsilon}(\theta,d)]+[d^{\varepsilon}(b_{1},\theta_{1})+d^{\varepsilon}(\theta_{1},d_{1})]-d^{\varepsilon}(d,d_{2})-d^{\varepsilon}(d_{1},d_{2})-2\eta$
$\displaystyle\geq\mathopen{}\mathclose{{}\left[\frac{d^{\varepsilon}(a,b)}{2}-\varepsilon+d^{\varepsilon}(\theta,d)}\right]+\mathopen{}\mathclose{{}\left[\frac{d^{\varepsilon}(a_{1},b_{1})}{2}-\varepsilon+d^{\varepsilon}(\theta_{1},d_{1})}\right]-d^{\varepsilon}(d,d_{2})-d^{\varepsilon}(d_{1},d_{2})-4\eta$
$\displaystyle\geq\frac{d^{\varepsilon}(a,b)}{2}+d^{\varepsilon}(\theta,d)+d^{\varepsilon}(\theta_{1},d_{1})-d^{\varepsilon}(d,d_{2})-d^{\varepsilon}(d_{1},d_{2})-2\varepsilon-4\eta,\text{
since }d^{\varepsilon}(a_{1},b_{1})\geq 0$

On the other hand, $d^{\varepsilon}(a,b)\geq d^{\varepsilon}(b,b_{1})$,
because
$d^{\varepsilon}(a,b)=\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(Y}\right)$
and $b,b_{1}\in Y$. So,

$d^{\varepsilon}(\theta,d)+d^{\varepsilon}(\theta_{1},d_{1})\leq\frac{d^{\varepsilon}(a,b)}{2}+d^{\varepsilon}(d,d_{2})+d^{\varepsilon}(d_{1},d_{2})+2\varepsilon+5\eta.$

From the triangle inequality, we can then write

$\displaystyle d^{\varepsilon}(\theta,\theta_{1})$ $\displaystyle\leq
d^{\varepsilon}(\theta,d)+d^{\varepsilon}(d,d_{1})+d^{\varepsilon}(d_{1},\theta_{1})$
$\displaystyle\leq\frac{d^{\varepsilon}(a,b)}{2}+d^{\varepsilon}(d,d_{2})+d^{\varepsilon}(d_{1},d_{2})+2\varepsilon+5\eta+d^{\varepsilon}(d,d_{1})$
$\displaystyle\leq\frac{d^{\varepsilon}(a,b)}{2}+[d^{\varepsilon}(d,d_{2})+d^{\varepsilon}(d_{1},d_{2})+d^{\varepsilon}(d,d_{1})]+2\varepsilon+5\eta$
$\displaystyle=\frac{d^{\varepsilon}(a,b)}{2}+3\times[3\delta({\mathcal{G}})+2]\varepsilon+2\varepsilon+5\eta$
$\displaystyle=\frac{\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(Y}\right)}{2}+[9\delta({\mathcal{G}})+8]\varepsilon+5\eta$

Since $\eta$ is arbitrary, we have the result. ∎

###  4.3. Homotopy Equivalence for Embedded Graphs

Similar to abstract metric graphs, the proof of homotopy equivalence result
for embedded metric graphs is devised using the barycentric subdivision.
Proceeding in the style of Subsection 3.2, we subdivide the Vietoris–Rips
complex of $(S,d^{\varepsilon})$, but possibly more than once. For a scale
$\beta>0$, we denote the Vietoris–Rips complex of $(S,d^{\varepsilon})$ by
$\mathcal{R}^{\varepsilon}_{\beta}(S)$.

We now assume that $S\subset{\mathbb{R}}^{d}$ and $\varepsilon>0$ be such that
the Hausdorff distance $d_{H}({\mathcal{G}},S)<\frac{\varepsilon}{4}$ . There
is a (possibly non-continuous and non-unique) vertex map
$\phi:{\mathcal{G}}\xrightarrow{\quad\quad}S$ such that
$\mathopen{}\mathclose{{}\left\lVert
a-\phi(a)}\right\rVert<\frac{\varepsilon}{4}$ for all $a\in{\mathcal{G}}$.
From Proposition 4.7, we note that for any $\beta>\varepsilon$ the vertex map
$\phi$ extends to a simplicial map:

(9)
$\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\xrightarrow{\quad\phi\quad}\mathcal{R}^{\varepsilon}_{\beta}(S).$

We show that the simplicial map $\phi$ is a homotopy equivalence for a
suitable choice $\beta$. We show in Lemma 4.11 and Lemma 4.12 that for any
$k\geq 0$, the simplicial map $\phi$ induces an isomorphism between the $k$–th
homotopy groups.

The following two lemmas prove that the simplicial map $\phi$ defined in (9)
induces injective and surjective homomorphisms on the homotopy groups. The
basepoint consideration has been ignored, as we observe from Proposition 4.7
that $d^{\varepsilon}$ is finite, since ${\mathcal{G}}$ is assumed to be path-
connected. As a result, the geometric complex of
$\mathcal{R}^{\varepsilon}_{\beta}(S)$ is path-connected, and so are all the
other complexes involved in our results.

######  Lemma 4.11 (Injectivity).

Let ${\mathcal{G}}\subset{\mathbb{R}}^{d}$ be an embedded metric graph. Let
$S\subset{\mathbb{R}}^{d}$ and $0<\varepsilon<\beta$ be such that

$4d_{H}({\mathcal{G}},S)<\varepsilon<\beta\leq\frac{2\rho(G)}{3\delta({\mathcal{G}})}.$

For any $k\geq 0$, the simplicial map
$\phi:\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\xrightarrow{\quad\quad}\mathcal{R}^{\varepsilon}_{\beta}(S)$
(as defined in (9)) induces an injective homomorphism on the $k$–th homotopy
group.

###### Proof.

Since $d_{H}({\mathcal{G}},S)<\frac{\varepsilon}{4}$, from Proposition 4.7 we
note the following chain of simplicial maps:

$\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\xrightarrow{\quad\phi\quad}\mathcal{R}^{\varepsilon}_{\beta}(S)\xrightarrow{\quad\psi\quad}\mathcal{R}_{\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\beta+\frac{\varepsilon}{2}}\right)}({\mathcal{G}}),$

such that $\mathopen{}\mathclose{{}\left\lVert
a-\phi(a)}\right\rVert<\frac{\varepsilon}{4}$ for all $a\in{\mathcal{G}}$ and
$\mathopen{}\mathclose{{}\left\lVert\psi(b)-b}\right\rVert<\frac{\varepsilon}{4}$
for all $b\in S$.

There is also the natural inclusion
$\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\xhookrightarrow{\quad
i\quad}\mathcal{R}_{\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\beta+\frac{\varepsilon}{2}}\right)}({\mathcal{G}})$.
We first claim that $(\psi\circ\phi)$ and $i$ are contiguous. To prove the
claim, take a $l$–simplex $\sigma_{l}=[a_{0},a_{1},\ldots,a_{l}]$ of
$\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})$. So,
$d_{\mathcal{G}}(a_{i},a_{j})<\frac{1}{2}(\beta-\varepsilon)$ for all $0\leq
i,j\leq l$. So, we have

$\displaystyle d_{\mathcal{G}}((\psi\circ\phi)(a_{i}),a_{j})$
$\displaystyle=d_{\mathcal{G}}(\psi(\phi(a_{i})),a_{j})$ $\displaystyle\leq
2d^{\varepsilon}(\phi(a_{i}),\phi(a_{j}))+\varepsilon,\text{ by
Proposition~{}\ref{prop:distances}}$
$\displaystyle\leq\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left[2d^{\varepsilon}(a_{i},a_{j})+\varepsilon+\frac{\varepsilon}{2}}\right]$
$\displaystyle<\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left[(\beta-\varepsilon)+\varepsilon+\frac{\varepsilon}{2}}\right]$
$\displaystyle=\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left[\beta+\frac{\varepsilon}{2}}\right]$

This implies that $(\psi\circ\phi)(\sigma_{l})\cup i(\sigma_{l})$ is a simplex
of
$\mathcal{R}_{\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\beta+\frac{\varepsilon}{2}}\right)}({\mathcal{G}})$.
Since $\sigma_{l}$ is an arbitrary simplex, the simplicial maps
$(\psi\circ\phi)$ and $i$ are contiguous. Consequently, the maps
$\big{\lvert}\psi\circ\phi\big{\rvert}$ and $\big{\lvert}i\big{\rvert}$ are
homotopic.

Since $\varepsilon<\beta$, we get

$\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left[\beta+\frac{\varepsilon}{2}}\right]<\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left[\beta+\frac{\beta}{2}}\right]=\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left[\frac{3\beta}{2}}\right]\leq\rho({\mathcal{G}}),$

from Theorem 2.5 there exist homotopy equivalences $T_{1},T_{2}$ such that the
following diagram commutes (up to homotopy):

$\big{\lvert}\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\big{\rvert}$$\big{\lvert}\mathcal{R}_{\delta({\mathcal{G}})\mathopen{}\mathclose{{}\left(\beta+\frac{\varepsilon}{2}}\right)}({\mathcal{G}})\big{\rvert}$${\mathcal{G}}$$\big{\lvert}i\big{\rvert}$$\big{\lvert}T_{1}\big{\rvert}$$\big{\lvert}T_{2}\big{\rvert}$

So, $\big{\lvert}i\big{\rvert}$ is also a homotopy equivalence. Hence, the
induced homomorphism $\big{\lvert}i\big{\rvert}_{*}$ on the homotopy groups is
an isomorphism. On the other hand,
$\big{\lvert}i\big{\rvert}\simeq\big{\lvert}\psi\circ\phi\big{\rvert}$.
Therefore, the induced homomorphism
$(\big{\lvert}\psi\big{\rvert}_{*}\circ\big{\lvert}\phi\big{\rvert}_{*})$ is
also an isomorphism, implying that $\big{\lvert}\phi\big{\rvert}_{*}$ is an
injective homomorphism. ∎

In order show surjectivity on homotopy groups, we again employ the idea of
simplicial subdivision.

######  Lemma 4.12 (Surjectivity).

Let ${\mathcal{G}}\subset{\mathbb{R}}^{d}$ be an embedded metric graph. Let
$S\subset{\mathbb{R}}^{d}$ and $0<\varepsilon<\beta$ be such that

$4d_{H}({\mathcal{G}},S)<\varepsilon<8\delta({\mathcal{G}})\alpha+2[\delta({\mathcal{G}})+1]\varepsilon\leq\beta<\frac{2\rho({\mathcal{G}})}{3\delta({\mathcal{G}})},$

where $\alpha=[9\delta({\mathcal{G}})+8]\varepsilon$. For any $k\geq 0$, the
simplicial map
$\phi:\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\xrightarrow{\quad\quad}\mathcal{R}^{\varepsilon}_{\beta}(S)$
(as defined in (9)) induces a surjective homomorphism on the $k$–th homotopy
group.

###### Proof.

As already remarked, the complexes
$\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})$ and
$\mathcal{R}^{\varepsilon}_{\beta}(S)$ are path-connected. So, the result
holds for $k=0$.

For $k\geq 1$, let us take an abstract simplicial complex ${\mathcal{K}}$ such
that $\big{\lvert}{\mathcal{K}}\big{\rvert}$ is a triangulation of the
$k$–dimensional sphere ${\mathbb{S}}^{k}$. In order to show surjectivity of
$\big{\lvert}\phi\big{\rvert}_{*}$, we start with a simplicial map
$g:{\mathcal{K}}\to\mathcal{R}^{\varepsilon}_{\beta}(S)$, and argue that there
is a natural number $N$ and a simplicial map
$\widetilde{g}:\mathrm{sd}^{N}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\xrightarrow{\quad\quad}\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})$
such that the following diagram commutes up to homotopy:

(10)
$\big{\lvert}\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\big{\rvert}$$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta}(S)\big{\rvert}$$\big{\lvert}{\mathcal{K}}\big{\rvert}$$\big{\lvert}\mathrm{sd}^{N}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$$\big{\lvert}\phi\big{\rvert}$$\big{\lvert}g\big{\rvert}$$\big{\lvert}\widetilde{g}\big{\rvert}$$h^{-1}$

where the linear homeomorphism
$h:\big{\lvert}\mathrm{sd}^{N}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}\xrightarrow{\quad\quad}\big{\lvert}{\mathcal{K}}\big{\rvert}$
maps each vertex of
$\mathrm{sd}^{N}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ to the
corresponding point of $\big{\lvert}{\mathcal{K}}\big{\rvert}$.

#### Step 1

We first note the effect of subdividing ${\mathcal{K}}$ once. We let
$\beta_{1}=\frac{\beta}{2}+\alpha$. We note that

$\displaystyle\beta_{1}$ $\displaystyle=\frac{\beta}{2}+\alpha$
$\displaystyle=\frac{\beta}{2}+\frac{\beta-[2\delta({\mathcal{G}})+2]\varepsilon}{8\delta({\mathcal{G}})},\text{
since }\beta\geq
8\delta({\mathcal{G}})\alpha+[2\delta({\mathcal{G}})+2]\varepsilon$
$\displaystyle\leq\frac{\beta}{2}+\frac{\beta}{8\delta({\mathcal{G}})}$
$\displaystyle\leq\frac{\beta}{2}+\frac{\beta}{2},\text{ since
}\delta({\mathcal{G}})\geq 1$ $\displaystyle=\beta.$

So, the inclusion in (11) is justified. Now, we show that there exists a
simplicial map
$g_{1}:\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\to\mathcal{R}^{\varepsilon}_{\beta_{1}}(S)$
such that the following diagram commutes upto homotopy:

(11)
$\big{\lvert}\mathcal{R}_{\beta_{1}}^{\varepsilon}(S)\big{\rvert}$$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta}(S)\big{\rvert}$$\big{\lvert}{\mathcal{K}}\big{\rvert}$$\big{\lvert}\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$$\big{\lvert}i\big{\rvert}$$\big{\lvert}g\big{\rvert}$$\big{\lvert}g_{1}\big{\rvert}$$h^{-1}$

We first note that each vertex of
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ is the
barycenter, $\widehat{\sigma_{k}}$, of a $k$–simplex $\sigma_{k}$ of
${\mathcal{K}}$. In order to construct the simplicial map
$\widetilde{g}:\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\xrightarrow{\quad\quad}\mathcal{R}^{\varepsilon}_{\beta}({\mathcal{G}})$,
we define it on the vertices
$\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$ first, and
prove that the vertex map extends to a simplicial map.

Let $\sigma_{k}=[a_{0},a_{1},\ldots,a_{k}]$ be a $k$–simplex of
${\mathcal{K}}$. Since $g$ is a simplicial map, we have that the image
$g(\sigma_{k})=[g(a_{0}),g(a_{1}),\ldots,g(a_{k})]$ is a subset of $S$ with
$\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(g(\sigma_{k})}\right)<\beta$.
We define

$g_{1}(\widehat{\sigma_{k}})\stackrel{{\scriptstyle
def}}{{=}}\theta_{\alpha}\mathopen{}\mathclose{{}\left(g(\sigma_{k})}\right).$

To see that $g_{1}$ extends to a simplicial map, consider a typical
$k$–simplex,
$\tau_{k}=[\widehat{\sigma_{0}},\widehat{\sigma_{1}},\ldots,\widehat{\sigma_{k}}]$,
of $\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)$, where
$\sigma_{i}\prec\sigma_{i+1}$ for $0\leq i\leq k-1$ and
$\sigma_{i}\in{\mathcal{K}}$. Now,

$\displaystyle\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(g_{1}(\tau_{k})}\right)$
$\displaystyle=\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left([\theta_{\alpha}\mathopen{}\mathclose{{}\left(g(\sigma_{0})}\right),\theta_{\alpha}\mathopen{}\mathclose{{}\left(g(\sigma_{1})}\right),\ldots,\theta_{\alpha}\mathopen{}\mathclose{{}\left(g(\sigma_{k})}\right)]}\right)$
$\displaystyle=\max_{0\leq i<j\leq
k}\\{d^{\varepsilon}(\theta_{\alpha}\mathopen{}\mathclose{{}\left(g(\sigma_{i})}\right),\theta_{\alpha}\mathopen{}\mathclose{{}\left(g(\sigma_{j})}\right))\\}$
$\displaystyle\leq\max_{0\leq j\leq
k}\mathopen{}\mathclose{{}\left\\{\frac{\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(g(\sigma_{j})}\right)}{2}+\alpha}\right\\},\text{
by Proposition~{}\ref{prop:center-alpha}}$
$\displaystyle\leq\frac{\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(g(\sigma_{k})}\right)}{2}+\alpha$
$\displaystyle<\frac{\beta}{2}+\alpha.$ $\displaystyle=\beta_{1}$

So, $g_{1}(\tau_{k})$ is a simplex of
$\mathcal{R}^{\varepsilon}_{\beta_{1}}(S)$. This implies that $g_{1}$ is a
simplicial map.

We invoke Proposition 2.2 to show that Diagram (11) commutes up to homotopy.
We need to argue that the simplicial maps $g$ and $(i\circ g_{1})$ satisfy the
conditions of Proposition 2.2:

  1. (a)

For any vertex $v\in{\mathcal{K}}$,

$(i\circ
g_{1})(v)=i(\theta_{\alpha}\mathopen{}\mathclose{{}\left(g(v)}\right))=i(g(v))=g(v).$

  2. (b)

For any simplex $\sigma=[a_{0},a_{1},\ldots,a_{k}]$ of ${\mathcal{K}}$, we
have for $0\leq i\leq k$

$\displaystyle d_{\varepsilon}(g(a_{i}),(i\circ g_{1})(\widehat{\sigma}))$
$\displaystyle=d_{\varepsilon}(g(a_{i}),\theta_{\alpha}\mathopen{}\mathclose{{}\left(g(\sigma)}\right))$
$\displaystyle=\frac{\mathrm{diam}_{\varepsilon}\mathopen{}\mathclose{{}\left(g(\sigma)}\right)}{2}+\alpha,\text{
from Proposition~{}\ref{prop:center-alpha}}$
$\displaystyle<\frac{\beta}{2}+\alpha=\beta_{1}\leq\beta.$

So, $g(\sigma)\cup(i\circ g_{1})(\widehat{\sigma})$ is a simplex of
$\mathcal{R}^{\varepsilon}_{\beta}(S)$.

Therefore, Proposition 2.2 implies that the diagram commutes.

#### Step 2

Choose a natural number $N$ such that $N\geq 2+\lg{\delta({\mathcal{G}})}$.
After $N$ subdivisions, we then have the following diagram:

(12)
$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta}(S)\big{\rvert}$$\big{\lvert}{\mathcal{K}}\big{\rvert}$$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta_{1}}(S)\big{\rvert}$$\big{\lvert}\mathrm{sd}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta_{2}}(S)\big{\rvert}$$\big{\lvert}\mathrm{sd}^{2}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta_{N}}(S)\big{\rvert}$$\big{\lvert}\mathrm{sd}^{N}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$$i$$\big{\lvert}g\big{\rvert}$$h^{-1}$$i$$\big{\lvert}g_{1}\big{\rvert}$$\big{\lvert}g_{2}\big{\rvert}$$h^{-1}$$i$$\big{\lvert}g_{N}\big{\rvert}$$h^{-1}$

where $\beta_{N}=\frac{\beta}{2^{N}}+\alpha\sum_{i=0}^{N-1}\frac{1}{2^{i}}$.
Moreover, the Diagram (12) commutes, since each smaller rectangle commutes as
shown in step 1.

#### Step 3

We also note that

$\displaystyle\beta_{N}$
$\displaystyle=\frac{\beta}{2^{N}}+\alpha\sum_{i=0}^{N-1}\frac{1}{2^{i}}$
$\displaystyle\leq\frac{\beta}{2^{N}}+2\alpha$
$\displaystyle\leq\frac{\beta}{4\delta({\mathcal{G}})}+2\alpha,\text{ since
}2^{N}\geq 4\delta({\mathcal{G}})$
$\displaystyle\leq\frac{\beta}{4\delta({\mathcal{G}})}+\mathopen{}\mathclose{{}\left[\frac{\beta}{4\delta({\mathcal{G}})}-\frac{2[1+\delta({\mathcal{G}})]\varepsilon}{4\delta({\mathcal{G}})}}\right],\text{
since }\beta\geq
8\delta({\mathcal{G}})\alpha+2[1+\delta({\mathcal{G}})]\varepsilon$
$\displaystyle=\frac{1}{2\delta({\mathcal{G}})}(\beta-\varepsilon)-\frac{\varepsilon}{2}$

This together with $Proposition~{}\ref{prop:distances}$ justify the simplicial
map $\psi$ in (13). Moreover, the inclusion $i$ in (12) is contiguous to
$(\phi\circ\psi)$. So, the following diagram commutes up to homotopy.

(13)
$\big{\lvert}\mathcal{R}_{\beta_{N}}^{\varepsilon}(S)\big{\rvert}$$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta}(S)\big{\rvert}$$\big{\lvert}{\mathcal{K}}\big{\rvert}$$\big{\lvert}\mathrm{sd}^{N}\mathopen{}\mathclose{{}\left({\mathcal{K}}}\right)\big{\rvert}$$\big{\lvert}\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\big{\rvert}$$\big{\lvert}\psi\big{\rvert}$$\big{\lvert}\phi\big{\rvert}$$\big{\lvert}g\big{\rvert}$$\big{\lvert}g_{N}\big{\rvert}$$h^{-1}$

Therefore, $\widetilde{g}=(\psi\circ g_{N})$ is the desired simplicial map.
Since $\big{\lvert}{\mathcal{K}}\big{\rvert}={\mathbb{S}}^{k}$ and $g$ is
arbitrary, we conclude that $\phi$ induces a surjective homomorphism on the
$k$–th homotopy group. ∎

######  Theorem 4.13 (Homotopy Equivalence under Hausdorff Distance).

Let ${\mathcal{G}}\subset{\mathbb{R}}^{d}$ be an embedded metric graph. Let
$S\subset{\mathbb{R}}^{d}$ and $0<\varepsilon<\beta$ be such that

$4d_{H}({\mathcal{G}},S)<\varepsilon<8\delta({\mathcal{G}})\alpha+2[\delta({\mathcal{G}})+1]\varepsilon\leq\beta<\frac{2\rho({\mathcal{G}})}{3\delta({\mathcal{G}})},$

where $\alpha=[9\delta({\mathcal{G}})+8]\varepsilon$. Then,
$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta}(S)\big{\rvert}\simeq{\mathcal{G}}$.

###### Proof.

By Lemma 4.11 and Lemma 4.12, for any $k\geq 0$

$\big{\lvert}\phi\big{\rvert}_{*}:\pi_{k}(\big{\lvert}\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\big{\rvert})\xrightarrow{\quad\quad}\pi_{k}(\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta}(S)\big{\rvert}).$

is an isomorphism, where the simplicial map is defined in (9). By the
Whitehead’s theorem, we have that $\big{\lvert}\phi\big{\rvert}$ is a homotopy
equivalence. On the other hand, since
$\frac{\beta-\varepsilon}{2}<\rho({\mathcal{G}})$, Theorem 2.5 implies that
$\big{\lvert}\mathcal{R}_{\frac{1}{2}(\beta-\varepsilon)}({\mathcal{G}})\big{\rvert}$
is homotopy equivalent to ${\mathcal{G}}$. Therefore, we conclude that
$\big{\lvert}\mathcal{R}^{\varepsilon}_{\beta}(S)\big{\rvert}\simeq{\mathcal{G}}$.
∎

##  5\. Conclusion

The current work succeeds in providing guarantees for a homotopy type recovery
of a metric graph from the Vietoris–Rips complexes of a metric space close to
it—both in Gromov–Hausdorff and Hausdorff distance. The study provokes a
number of interesting future research directions. Metric graphs are the
simplest, albeit interesting, class of geodesic spaces one can consider. It is
reasonable to believe that recovery of a more general geodesic space, in the
same vein, must require an explicit knowledge of its curvature bounds. To the
best of the author’s knowledge, it is not known, even for a two-dimensional
Riemannian manifold, how to choose a suitable scale for the Vietoris–Rips
complex of a metric space Gromov–Hausdorff close it. Although we provide a
homotopy equivalent recovery of an embedded metric graph, the resulting
complex $\mathcal{R}^{\varepsilon}_{\beta}(S)$, being a very high-dimensional
object without a natural embedding, does not lend itself well to practical
applications. Since $S$ is a subset ${\mathbb{R}}^{d}$, one can consider the
shadow (as defined in [8]) of the complex as a _reconstruction_ of
${\mathcal{G}}$. As pointed out in [8, Proposition 5.3], the shadow of a
complex is notorious for being topologically unfaithful. When the Hausdorff
between $S$ and ${\mathcal{G}}$ is very small, however, we conjecture to have
homotopy equivalent shadow of $\mathcal{R}^{\varepsilon}_{\beta}(S)$, hence
providing a homotopy equivalent reconstruction of ${\mathcal{G}}$ with an
embedding in the same ambient.

#### Acknowledgments

The author would like to thank the school of information at the University of
California, Berkeley, where this work was completed, for all its support.

## References

  * [1] Usgs earthquake hazards program.
  * [2] Mridul Aanjaneya, Frédéric Chazal, Daniel Chen, Marc Glisse, Leonidas Guibas, and Dmitriy Morozov.  Metric graph reconstruction from noisy data.  International Journal of Computational Geometry & Applications, 22(04):305–325, 2012.
  * [3] Michał Adamaszek, Henry Adams, and Florian Frick.  Metric reconstruction via optimal transport.  SIAM Journal on Applied Algebra and Geometry, 2:597–619, 2018.
  * [4] Henry Adams and Joshua Mirth.  Metric thickenings of Euclidean submanifolds.  Topology and its Applications, 254:69–84, Mar 2019.
  * [5] Mahmuda Ahmed, Brittany Terese Fasy, Matt Gibson, and Carola Wenk.  Choosing thresholds for density-based map construction algorithms.  In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’15, pages 24:1–24:10, New York, NY, USA, 2015. ACM.
  * [6] Dominique Attali, André Lieutier, and David Salinas.  Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes.  Computational Geometry, 46(4):448 – 465, 2013.  27th Annual Symposium on Computational Geometry (SoCG 2011).
  * [7] Dmitri Burago, Yuri Burago, and Sergei Ivanov.  A Course in Metric Geometry, volume 33 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, Rhode Island, June 2001.
  * [8] Erin W. Chambers, Vin de Silva, Jeff Erickson, and Robert Ghrist.  Vietoris–Rips complexes of planar point sets.  Discrete & Computational Geometry, 44(1):75–90, Jul 2010.
  * [9] Frédéric Chazal and S. Y. Oudot.  Towards persistence-based reconstruction in Euclidean spaces.  In Proc. 24th ACM Sympos. Comput. Geom., pages 232–241, 2008.
  * [10] Tamal K. Dey, Jiayuan Wang, and Yusu Wang.  Graph reconstruction by discrete Morse theory.  In 34th International Symposium on Computational Geometry, pages 31:1–31:15, 2018.
  * [11] Herbert Edelsbrunner.  Alpha shapes — a survey.  2009\.
  * [12] Brittany Terese Fasy, Rafal Komendarczyk, Sushovan Majhi, and Carola Wenk.  On the Reconstruction of Geodesic Subspaces of $\mathbb{R}^{n}$.  arXiv:1810.10144 [math.AT], 2018.
  * [13] M. Gromov.  Hyperbolic Groups, pages 75–263.  Springer New York, New York, NY, 1987.
  * [14] Allen Hatcher.  Algebraic Topology.  Cambridge University Press, First edition, 2002.
  * [15] Jean-Claude Hausmann.  On the Vietoris-Rips Complexes and a Cohomology Theory for Metric Spaces.  In Frank Quinn, editor, Prospects in Topology (AM-138), Proceedings of a Conference in Honor of William Browder. (AM-138), pages 175–188. Princeton University Press, 1995.
  * [16] Jisu Kim, Jaehyeok Shin, Frédéric Chazal, Alessandro Rinaldo, and Larry Wasserman.  Homotopy reconstruction via the Čech complex and the Vietoris-Rips complex.  In 36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [17] J. Latschev.  Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold.  Archiv der Mathematik, 77(6):522–528, December 2001.
  * [18] Fabrizio Lecci, Alessandro Rinaldo, and Larry Wasserman.  Statistical analysis of metric graph reconstruction.  J. Mach. Learn. Res., 15(1):3425–3446, January 2014.
  * [19] James R. Munkres.  Elements Of Algebraic Topology.  Addison-Wesley Publishing Company, Second edition, 1996.
  * [20] Vin De Silva.  A weak definition of delaunay triangulation.  2003\.
  * [21] Edwin H Spanier.  Algebraic topology, volume 55.  Springer Science & Business Media, 1994.
  * [22] L. Vietoris.  Über den höheren zusammenhang kompakter räume und eine klasse von zusammenhangstreuen abbildungen.  Mathematische Annalen, 97:454–472, 1927.