Lower Bounding the Gromov–Hausdorff distance in Metric Graphs

We obtain results for both research directions (A) and (B) in the case of metric graphs. Namely, we provide conditions ensuring that the Hausdorff and Gromov–Hausdorff distances between the ambient space and a sample coincide, and we derive bounds for the Gromov–Hausdorff distance between two sufficiently dense samples. Given the independent relevance of both kinds of contributions, we present many of our results with an item (a) and (b) dedicated to each.

Let $G$ be a connected, compact metric graph with finitely many edges, and let $X\subseteq G$ be a subset. We show how to lower bound the Gromov–Hausdorff distance $d_{\mathrm{GH}}(G,X)$ in terms of constant multiplier times the Hausdorff distance $d_{\mathrm{H}}(G,X)$, namely $d_{\mathrm{GH}}(G,X)\geq C\cdot d_{\mathrm{H}}(G,X)$. We often obtain the optimal value $C=1$. Since the reverse inequality $d_{\mathrm{GH}}(G,X)\leq d_{\mathrm{H}}(G,X)$ always holds, the inequality $d_{\mathrm{GH}}(G,X)\geq d_{\mathrm{H}}(G,X)$ (with optimal constant $C=1$) immediately gives equality $d_{\mathrm{GH}}(G,X)=d_{\mathrm{H}}(G,X)$.

The simplest metric graph is a tree. Let $\vec{d}_{\mathrm{H}}(\partial T,X)$ denote the directed Hausdorff distance from the leaves of $T$ to the sample $X$ (see Section 2). We show the following. {restatable*}[Metric Trees]thmtrees Let $(T,d)$ be a compact metric tree. For any $X,Y\subseteq T$,

1. (a)

   if $d_{\mathrm{H}}(T,X)>\vec{d}_{\mathrm{H}}(\partial T,X)$, then $d_{\mathrm{GH}}(T,X)=d_{\mathrm{H}}(T,X)$, and

2. (b)

   for any $\varepsilon\geq d_{\mathrm{H}}(T,Y)$, if $d_{\mathrm{H}}(X,Y)>\vec{d}_{\mathrm{H}}(\partial T,X)+\varepsilon$, then $d_{\mathrm{GH}}(X,Y)\geq d_{\mathrm{H}}(X,Y)-2\varepsilon$.

The interpretation of part (a) of Theorem 1.1 is as follows: if the biggest gaps in the sampling $X\subseteq T$ are not near the leaves of $T$, then $d_{\mathrm{GH}}(T,X)=d_{\mathrm{H}}(T,X)$.

The following theorem shows that some control on the set of leaf vertices of $T$ is needed.

thmcounterEx For any $\varepsilon>0$ there exists a compact metric tree $T$ and a closed subset $X\subseteq T$ such that $d_{\mathrm{GH}}(T,X)\leq\varepsilon\cdot d_{\mathrm{H}}(T,X)$.

When $G=S^{1}$ is the circle of circumference $2\pi$, the authors of [2] showed that if $d_{\mathrm{GH}}(S^{1},X)<\frac{\pi}{6}$, then $d_{\mathrm{GH}}(S^{1},X)=d_{\mathrm{H}}(S^{1},X)$. The question of the optimality of the density constant $\frac{\pi}{6}$ was subsequently raised. In this paper, we show that $\frac{\pi}{6}$ is suboptimal: the optimal density constant is in fact $\frac{\pi}{3}$. The first result below shows that the new weaker assumption $d_{\mathrm{GH}}(S^{1},X)<\frac{\pi}{3}$ is necessary, and the second result shows it is sufficient.

[Optimality of $\frac{\pi}{3}$]thmoptimality For any $\varepsilon\in\left(0,\frac{\pi}{6}\right)$, there exists a nonempty compact subset $X\subseteq S^{1}$ with $d_{\mathrm{H}}(S^{1},X)=\frac{\pi}{3}+\varepsilon$ and $d_{\mathrm{GH}}(S^{1},X)=\frac{\pi}{3}<d_{\mathrm{H}}(S^{1},X)$.

[The Circle]thmsufficient For any subsets $X,Y\subseteq S^{1}$, we have

1. (a)

   $d_{\mathrm{GH}}(S^{1},X)\geq\min\left\{d_{\mathrm{H}}(S^{1},X),\ \tfrac{\pi}{3}\right\}$, and

2. (b)

   $d_{\mathrm{GH}}(X,Y)\geq\min\left\{d_{\mathrm{H}}(X,Y)-2\varepsilon,\ \tfrac{\pi}{3}-\varepsilon\right\}$ for any $\varepsilon\geq d_{\mathrm{H}}(S^{1},Y)$.

We generalize the above results for the circle and trees to general metric graphs. Let $G$ be a compact metric graph and let $e(G)$ be the shortest edge length between non-leaf vertices (see (2)). We prove that if $X$ is dense enough relative to the smallest edge length $e(G)$, then the Gromov–Hausdorff distance matches the Hasudorff distance.

[Metric Graphs]thmgraphs Let $(G,d)$ be a compact, connected metric graph. Let $X,Y\subseteq G$ be subsets such that $d_{\mathrm{H}}(G,X)>\vec{d}_{\mathrm{H}}(\partial G,X)$ if $\partial G\neq\emptyset$. Then

1. (a)

   $d_{\mathrm{GH}}(G,X)\geq\min\left\{d_{\mathrm{H}}(G,X),\tfrac{1}{12}e(G)\right\}$, and

2. (b)

   $d_{\mathrm{GH}}(X,Y)\geq\min\left\{d_{\mathrm{H}}(X,Y)-2\varepsilon,\tfrac{1}{12}e(G)-\varepsilon\right\}$ for any $\varepsilon\geq d_{\mathrm{H}}(G,Y)$.

We begin in Section 2 with background and notation. In Section 3, we provide an example showing that some control over the boundary of the metric graph is necessary. We begin with the case of metric trees in Section 4, proceeding next to the case of the circle in Section 5, and finally general metric graphs in Section 6.

Let $(X,d)$ be a metric space. For any $x\in X$, we let $B(x;r)=\{x^{\prime}\in X~{}|~{}d(x,x^{\prime})<r\}$ denote the metric ball of radius $r$ about $x$. If needed for the sake of clarity, we will sometimes write $B_{X}(x;r)$ instead of $B(x;r)$. For any $r\geq 0$ and $A\subseteq X$, we let

denote the $r$-thickening of $A$ in $X$, namely, the union of open metric balls of radius $r$ centered at the points of $A$.

The diameter of a subset $A\subseteq X$ is the supremum of all distances between pairs of points of $A$. More formally, the diameter is defined as

The diameter of a compact set $A$ is always finite.

We follow Definitions 3.1.12 (quotient metric) and 3.2.9 (metric graph) of [5] in order to define a metric graph. A metric segment is a metric space isometric to a real line segment $[0,l]$ for $l\geq 0$. Our metric graphs will always be connected and have a finite number of vertices and edges.

The metric segments $e\in E$ are called the edges and the equivalence classes of their endpoints in $V$ are called the vertices of $G$. Since $G$ is connected, we have $d(\xi,\xi^{\prime})<\infty$ for all $\xi,\xi^{\prime}\in G$. Since $E$ is finite, the quotient semi-metric [5, Definition 3.1.12] is in fact a metric.¹¹1 One needs to be more careful if $E$ is infinite. Indeed, suppose one has two vertices $v$ and $v^{\prime}$, and one edge $e_{n}$ of length $\frac{1}{n}$ for each $n\in\mathbb{N}$ with endpoints $v$ and $v^{\prime}$. Then the quotient semi-metric gives $d(v,v^{\prime})=\inf_{n\in\mathbb{N}}\frac{1}{n}=0$, even though $v\neq v^{\prime}$, and hence this semi-metric is not a metric. These subtleties disappear since we assume $E$ is finite.

For 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 between the endpoints of $e$ according to the metric $d$. Extending the definition of length for a continuous path $\gamma:[a,b]\to G$, we define the length $l(\gamma)$ as the sum of the (full or partial) lengths of the edges that $\gamma$ traverses.

For a vertex $v$ of a graph, its degree, denoted $deg(v)$, is the number of edges incident to $v$. A self-loop at $v$ contributes $2$ to the degree of $v$. As an example, the circle $S^{1}$ can be given a metric graph structure by assigning a single vertex $v$ at the north pole, of degree $2$, having a self-loop.

A metric graph $G$ is therefore endowed with two layers of information: a metric structure turning it into a length space [5, Definition 2.1.6] and a combinatorial structure $(V,E)$ as an abstract graph. Using the above definition, we are also allowing $G$ to have single-edge cycles and multiple edges between a pair of vertices. In this paper, we only consider path-connected, compact metric graphs $(G,d)$ with finitely many edges. The metric graphs we consider are automatically geodesic (i.e., for every $x,y\in G$ there is an isometric embedding $\gamma\colon[0,d(x,y)]\to G$ such that $\gamma(0)=x$ and $\gamma(d(x,y))=y$) since they are compact (a compact length space is geodesic). This justifies why there is always at least one shortest path between two points.

For a pair of points $\xi,\xi^{\prime}\in G$, there always exists a shortest path or geodesic path $\gamma$ in $G$ joining $\xi,\xi^{\prime}$ whose length satisfies $l(\gamma)=d(\xi,\xi^{\prime})$. We define an undirected simple loop $\mathcal{\gamma}$ of $G$ to be a simple path that intersects itself only at the endpoints. We denote by $\mathcal{L}(G)$ the set of all simple loops of $G$. Since $G$ is assumed to have finitely many edges, the set $\mathcal{L}(G)$ is finite. Since a metric tree is defined as a metric graph with no loops, $\mathcal{L}(G)=\emptyset$ for a metric tree $G$.

For a metric graph $(G,d)$ with $\mathcal{L}(G)\neq\emptyset$, let $e(G)$ denote the length of the smallest non-terminal edge:

Let $(Z,d)$ be a metric space. If $X$ and $Y$ are two subsets of $Z$, then the directed Hausdorff distance from $X$ to $Y$, denoted $\vec{d}_{\mathrm{H}}(X,Y)$, is defined by

Note that $\vec{d}_{\mathrm{H}}(X,Y)$ is not symmetric in general.

To retain symmetry, the Hausdorff distance, denoted $d_{\mathrm{H}}(X,Y)$, is defined as

In other words, the Hausdorff distance finds the infimum over all real numbers $r$ such that if we thicken $Y$ by $r$ it contains $X$ and if we thicken $X$ by $r$ it contains $Y$. If no such $r$ exists then the Hausdorff distance is infinity.

Let $X,Y$ be non-empty sets. A relation $\mathcal{R}\subseteq X\times Y$ is called a correspondence if the following two conditions hold: for every $x\in X$ there exists some $y\in Y$ with $(x,y)\in\mathcal{R}$, and for every $y\in Y$ there exists some $x\in X$ exists with $(x,y)\in\mathcal{R}$.

If $\mathcal{R}$ is a correspondence between $(X,d_{X})$ and $(Y,d_{Y})$, then the distortion of $\mathcal{R}$ is:

The Gromov–Hausdorff distance between two (arbitrary) metric spaces $X$ and $Y$ to be

where the infimum is taken over all correspondences $\mathcal{R}$ between $X$ and $Y$ [5, 12]. As shown in  [10], if $X$ and $Y$ are both compact metric spaces, a distortion-minimizing correspondence in the definition of $d_{\mathrm{GH}}(X,Y)$ always exists.

The above definition immediately provides the following simple lower bound on the Gromov–Hausdorff distance between two compact metric spaces $X$ and $Y$.

Let $Z_{1},Z_{2}$ be metric spaces and $\mathcal{R}\subseteq Z_{1}\times Z_{2}$ be a correspondence. For a subset $A\subseteq Z_{1}$, we define the following subset of $Z_{2}$:

Similarly, for a subset $A\subseteq Z_{2}$, we define the following subset of $Z_{1}$:

Using the notation above, we observe the following fact.

The subset $A\neq\emptyset$ since for any $\xi\in S^{1}$, either $\xi\in A$ or $\widehat{\xi}\in A$. For the same reason, $B\neq\emptyset$.

We argue that $A$ is an open subset of $S^{1}$. Let $\xi\in A$ be arbitrary. Let $x\in\mathcal{R}[\xi]$ and $\widehat{x}\in\mathcal{R}[\widehat{\xi}]$ be such that $a\preceq x\preceq\widehat{x}\preceq b$.

Fix small $\zeta\geq 0$ such that $\mathrm{dis}(\mathcal{R})+\zeta<2r$. We will show that $\xi^{\prime}\in A$ for any $\xi^{\prime}\in S^{1}$ with $d(\xi,\xi^{\prime})\leq\zeta$. We note that $d(\hat{\xi},\hat{\xi^{\prime}})=d(\xi,\xi^{\prime})\leq\zeta$. Let us choose $x^{\prime}\in\mathcal{R}[\xi^{\prime}]$ and $\widehat{x^{\prime}}\in\mathcal{R}[\widehat{\xi^{\prime}}]$. It suffices to show that $a\preceq x^{\prime}\preceq\widehat{x^{\prime}}\preceq b$. Without any loss of generality, we assume that $a\preceq x\preceq x^{\prime}\preceq b$. The configuration is shown in Figure 5(b). We have

Since $d(x,x^{\prime})<2r$, a unique shortest path joining $x,x^{\prime}$ exists and is contained in $\eta$. The same fact is also true for $\widehat{x},\widehat{x^{\prime}}$, since

On the other hand, $d(x,\widehat{x})\geq d(\xi,\widehat{\xi})-\mathrm{dis}(\mathcal{R})>\pi-2r$. Similarly, $d(x^{\prime},\widehat{x^{\prime}})>\pi-2r$. Also, we have