---
abstract: 'The Gromov-Hausdorff distance $(d_{GH})$ proves to be a useful distance measure between shapes. In order to approximate $d_{GH}$ for compact subsets $X,Y\subset\R^d$, we look into its relationship with $d_{H,iso}$, the infimum Hausdorff distance under Euclidean isometries. As already known for dimension $d\geq 2$, the $d_{H,iso}$ cannot be bounded above by a constant factor times $d_{GH}$. For $d=1$, however, we prove that $d_{H,iso}\leq\frac{5}{4}d_{GH}$. We also show that the bound is tight. In effect, this gives rise to an $O(n\log{n})$-time algorithm to approximate $d_{GH}$ with an approximation factor of $\left(1+\frac{1}{4}\right)$.'
author:
- 'Sushovan Majhi[^1][^2]'
- Jeffrey Vitter
- 'Carola Wenk$^\dag$'
bibliography:
- 'main.bib'
title: 'Approximating Gromov-Hausdorff Distance in Euclidean Space'
---

Introduction {#sec:intro}
============

This paper grew out of our effort to compute the Gromov-Hausdorff distance between Euclidean subsets. The Gromov-Hausdorff distance between two abstract metric spaces was first introduced by M. Gromov in ICM 1979 (see Berger [@berger_encounter_2000]). The notion, although it emerged in the context of Riemannian metrics, proves to be a natural distance measure between any two (compact) metric spaces. Only in the last decade the Gromov-Hausdorff distance has received much attention from the researchers in the more applied fields. In shape recognition and comparison, shapes are regarded as metric spaces that are deformable under a class of transformations. Depending on the application in question, a suitable class of transformations is chosen, then the dissimilarity between the shapes are defined by a suitable notion of *distance measure or error* that is invariant under the desired class of transformations. For comparing Euclidean shapes under Euclidean isometry, the use of Gromov-Hausdorff distance is proposed and discussed in [@memoli_theoretical_2005; @memoli_use_nodate; @memoli_gromov-hausdorff_2008; @memoli_properties_2012].

In this paper, we are primarily motivated by the questions pertaining to the computation of the Gromov-Hausdorff distance, particularly between Euclidean subsets. Although the distance measure puts the Euclidean shape matching on a robust theoretical foundation [@memoli_theoretical_2005; @memoli_use_nodate], the question of computing the Gromov-Hausdorff distance, or even an approximation thereof, still remains elusive. In the recent years, some efforts have been made to address such computational aspects. Most notably, the authors of [@agarwal_computing_2015] show an NP-hardness result for approximating the Gromov-Hausdorff distance between metric trees. For Euclidean subsets, however, the question of a polynomial time algorithm is still open. In [@memoli_properties_2012], the author shows that computing the distance is related to various NP-hard problems and studies a variant of Gromov-Hausdorff distance.

#### Background and Related Work

The notion of Gromov-Hausdorff distance is closely related to the notion of Hausdorff distance. Let $(Z,d_Z)$ be any metric space. We first give a formal definition of the directed Hausdorff distance between any two subsets of $Z$.

\[def:dh\] For any two compact subsets $X,Y$ of a metric space $(Z,d_Z)$, the from $X$ to $Y$, denoted $\overrightarrow{d}_H^Z(X,Y)$, is defined by $$\sup_{x\in X}\inf_{y\in Y}d_Z(x,y).$$

Unfortunately, the directed Hausdorff distance is not symmetric. To retain symmetry, the is defined in the following way:

\[def:h\] For any two compact subsets $X,Y$ of a metric space $(Z,d_Z)$, their , denoted $d_H^Z(X,Y)$, is defined by $$\max\left\{\overrightarrow{d}_H^Z(X,Y),\overrightarrow{d}_H^Z(Y,X)\right\}.$$

To keep our notations simple, we drop the superscript when it is understood that $Z$ is taken to be $\R^d$ and $X,Y$ are Euclidean subsets equipped with the standard Euclidean metric $\mod{\cdot}$. The $d_{H}$ can be computed in $O(n\log{n})$-time for finite point sets with at most $n$ points; see [@Alt1995].

We are now in a place to define the Gromov-Hausdorff distance formally. Unlike the Hausdorff distance, the Gromov-Hausdorff distance can be defined between two abstract metric spaces $(X,d_X)$ and $(Y,d_Y)$ that may not share a common ambient space. We start with the following formal definition:

\[def:gh\] The , denoted $d_{GH}(X,Y)$, between two metric spaces $(X,d_X)$ and $(Y,d_Y)$ is defined to be $$d_{GH}(X,Y)=\inf_{\substack{f:X\to Z \\g:Y\to Z\\ Z}}d_H^Z(f(X),g(Y)),$$ where the infimum is taken over all isometries $f:X\to Z$, $g:Y\to Z$ and metric spaces $(Z,d_Z)$.

In order to present an equivalent definition of the Gromov-Hausdorff distance that is computationally viable, we first define the notion of a correspondence.

\[def:cor\] A $\C$ between any two (non-empty) sets $X$ and $Y$ is defined to be a subset $\C\subseteq X\times Y$ with the following two properties:

i)  for any $x\in X$, there exists an $y\in Y$ such that $(x,y)\in\C$, and

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

A correspondence $\C$ is a special *relation* that assigns all points of both $X$ and $Y$ a corresponding point. If the sets $X$ and $Y$ in the are equipped with metrics $d_X$ and $d_Y$ respectively, we can also define the distortion of the correspondence $\C$.

Let $\C$ be a correspondence between two metric spaces $(X,d_X)$ and $(Y,d_Y)$, then its , denoted $Dist(\C)$, is defined to be $$\sup_{(x_1,y_1),(x_2,y_2)\in\C}\mod{d_X(x_1,x_2)-d_Y(y_1,y_2)}$$

The distortion $Dist(\C)$ is sometimes called the *additive* distortion as opposed to the *multiplicative* distortion; see [@kenyon_low_2010] for a definition. For non-empty sets $X,Y$, we denote by $\C(X,Y)$ the set of all correspondences between $X$ and $Y$. We note the following relation, which can be used to give an equivalent definition of the Gromov-Hausdorff distance via correspondences. For a proof of the following, the readers are encouraged to see [@burago_course_2001].

For any two compact metric spaces $(X,d_X)$ and $(Y,d_Y)$, the following relation holds: $$d_{GH}(X,Y)=\frac{1}{2}\inf\limits_{\C\in\C(X,Y)} Dist(\C)$$

This work is primarily motivated by the question of approximating the Gromov-Hausdorff distance between compact sets $X,Y\subset\R^d$. In [@memoli_gromov-hausdorff_2008], the authors use a related notion $d_{H,iso}$ in an effort to bound the Gromov-Hausdorff distance in the Euclidean case. For any $d\geq1$, a Euclidean isometry $T:\R^d\to\R^d$ is defined to be a map that preserves the distance, i.e., $\mod{T(a)-T(b)}=\mod{a-b}~\forall a,b\in\R^d$. When $d=1$, the $T$ can only afford to be a translation or a reflection (flip). In $d=2$, a Euclidean isometry is characterized by a combination of a translation, a rotation by an angle, or a mirror-reflection. For more about Euclidean isometries, see [@artin2011algebra]. We denote by $\E(\R^d)$ the set of all isometres of $\R^d$.

\[def:hiso\] For any two compact subsets $X,Y$ of $\R^d$, we define $d_{H,iso}(X,Y)$ to be $$\inf\limits_{T\in\mathcal{E}(\R^d)} d_H(X,T(Y)).$$

The authors show in [@memoli_gromov-hausdorff_2008] the following bounds, relating $d_{H,iso}$ and $d_{GH}$ between two compact subsets $X,Y$ of $\R^d$. $$\label{eqn:memoli}
  d_{GH}(X,Y)\leq d_{H,iso}(X,Y)\leq c'_d(M)^\frac{1}{2}\sqrt{d_{GH}(X,Y)},$$ where $M=\max\big\{\mbox{diameter}(X),\mbox{diameter}(Y)\big\}$ and $c'_d$ is a constant that depends only on the dimension $d$.

In the inequality , note the upper bound depends on the diameter of the input sets $X$ and $Y$. For $d\geq 2$, such a dependence is unavoidable. For $d=1$, however, we show such a dependence disappears giving rise to an approximation algorithm to approximate $d_{GH}$ with $d_{H,iso}$.

#### Our Contribution

Our main contribution in this work is to provide a satisfactory answer to the quest of understanding the relation between $d_{H,iso}$ and $d_{GH}$ when $X,Y$ are compact subsets of $\R^1$ equipped with the standard Euclidean metric.

In , we show that $d_{H,iso}(X,Y)\leq\frac{5}{4}d_{GH}(X,Y)$ for any compact $X,Y\subset\R^1$. For subsets of the real line, it was believed for a long time that $d_{GH}=d_{H,iso}$. We show in that this is, in fact, not true by showing that the bound $\frac{5}{4}$ in is tight. Since $d_{H,iso}(X,Y)$ can be computed in $O(n\log{n})$-time ([@ROTE1991123]), we provide an $O(n\log{n})$-time algorithm to approximate $d_{GH}(X,Y)$ for finite $X,Y\subset\R^1$ with an approximation factor of $(1+\frac{1}{4})$.

Approximating Gromov-Hausdorff Distance in $\R^1$ {#sec:1d}
=================================================

This section is devoted to our main result () on approximating the Gromov-Hausdorff distance between subsets of the real line. Unless stated otherwise, in this section we always assume that $X,Y$ are compact subsets of $\R^1$ and both are equipped with the standard Euclidean metric denoted by $\mod{\cdot}$.\
In $\R^1$ it often helps to visualize $X\times Y$ on the disjoint union of two real lines in $\R^2$ and a correspondence $\C\in\C(X,Y)$ by edges between the corresponding points; see . Such a two dimensional visualization comes in handy for the proofs.

For a correspondence $\C\in\C(X,Y)$, we say a pair of edges $(x_1,y_1)$ and $(x_2,y_2)$ are if they cross in the usual sense, i.e., either of the following happens $x_1<x_2$ but $y_1>y_2$ or $x_1>x_2$ but $y_1<y_2$; see .

[0.45]{} ![On the left, the (sorted) $X=\{x_1,x_2\}$ and $Y=\{y_1,y_2,y_3\}$ are identified as subsets of the top and the bottom lines respectively. The points of $X$ are shown in green, and the points of $Y$ are shown in yellow. We visualize the correspondence $\C=\{(x_1,y_1),(x_2,y_2),(x_2,y_3)\}$ by the red edges between the respective points. Also, the edges $(x_1,y_1)$ and $(x_2,y_2)$ are crossing. On the right, the distortion $D$ of a correspondence is attained by the pairs $(x',y')$ and $(x,y)$.[]{data-label="fig:visual"}](visual.pdf "fig:")

[0.45]{} ![On the left, the (sorted) $X=\{x_1,x_2\}$ and $Y=\{y_1,y_2,y_3\}$ are identified as subsets of the top and the bottom lines respectively. The points of $X$ are shown in green, and the points of $Y$ are shown in yellow. We visualize the correspondence $\C=\{(x_1,y_1),(x_2,y_2),(x_2,y_3)\}$ by the red edges between the respective points. Also, the edges $(x_1,y_1)$ and $(x_2,y_2)$ are crossing. On the right, the distortion $D$ of a correspondence is attained by the pairs $(x',y')$ and $(x,y)$.[]{data-label="fig:visual"}](standard-1.pdf "fig:")

For a correspondence $\C\in\C(X,Y)$ between two compact sets with $Dist(\C)=D$, there exists a pair of edges $(x',y'),(x,y)\in\C$ such that $\bigmod{\mod{x-x'}-\mod{y-y'}}=D$. We can further assume, without loss of generality, that $x\geq x'$ and $(x-x')\leq\mod{y-y'}$. Then, there exists an isometry $T\in\E(\R^1)$ such that the edges $(x',T(y'))$ and $(x,T(y))$ do not cross and $\big(x'-T(y')\big)=\big(T(y)-x\big)=\frac{D}{2}$; see . From now on, we always assume this standard configuration for any given compact $X,Y\subset\R^1$ and a correspondence $\C$ between them.\
Now, we present in our main result of this section. We also know that $d_{GH}(X,Y)\leq d_{H,iso}(X,Y)$ for any compact $X,Y\subset\R^d$; see [@memoli_gromov-hausdorff_2008]. Together with this, thus gives us the approximation algorithm for $d_{GH}$ with an approximation factor of $\left(1+\frac{1}{4}\right)$. Later in , we also show that the upper bound of is tight.

\[thm:gh\] For any two compact $X,Y\subset\R^1$ we have $$d_{H,iso}(X,Y)\leq\frac{5}{4}d_{GH}(X,Y).$$

In order to prove the result, it suffices to show that for any correspondence $\C\in\C(X,Y)$ with $Dist(\C)=D$, there exists a Euclidean isometry $T\in\mathcal{E}(\R^1)$ such that $$d_H(X,T(Y))\leq\frac{5D}{8}.$$ Depending on the crossing behavior, we classify a given correspondence into three main types: no double crossing, wide crossing, and no wide crossing, and we divide the proof for each type into , , and respectively.

We start with the definition of a double crossing edge.

An edge in a correspondence $\C\in\C(X,Y)$ is said to be if it crosses both the (designated) edges $(x',y')$ and $(x,y)$; see .

In the following, we consider the case when there is no double crossing edge in $\C$.

\[thm:no-cross\] For a correspondence $\C\in\C(X,Y)$ without any double crossing, there exists a value $\Delta\in\R$ such that $$d_H(X,Y+\Delta)\leq\frac{5}{8}D,$$ where $D=Dist(\C)$.

In the trivial case, when $d_H(X,Y)\leq\frac{5}{8}D$, we take $\Delta=0$. So, we assume the non-trivial case that $d_H(X,Y)>\frac{5}{8}D$. Therefore, there exists either i) $a_0\in X$ with $\min\limits_{b\in Y}\mod{a_0-b}>\frac{D}{2}$ or ii) $b_0\in Y$ with $\min\limits_{a\in X}\mod{a-b_0}>\frac{D}{2}$, or both.

We first note that such an $a_0$ cannot belong to $[x',x]$, where $Dist(C)=\bigmod{\mod{y-y'}-\mod{x-x'}}$. If it did, then for any edge $(a_0,t)\in\C$, we would have $t\in[y',y]$ and $\mod{a_0-t}\leq\frac{D}{2}$ because then either $\bigmod{\mod{a_0-x'}-\mod{t-y'}}\geq\frac{D}{2}$ or $\bigmod{\mod{a_0-x}-\mod{t-y}}\geq\frac{D}{2}$. In fact, $a_0$ has to belong to $A$ or $A'$ as defined below (see ): $$\begin{aligned}
  A&=\{p\in X\cap(x+D,\infty)\mid\mbox{ there exists }q\in Y\cap[y',y]\mbox{ with }(p,q)\in\C\},\\
  A'&=\{p\in X\cap(-\infty,x'-D)\mid\mbox{ there exists }q\in Y\cap[y',y]\mbox{ with }(p,q)\in\C\}.
  \end{aligned}$$

Similarly if $b_0$ exists, it has to belong to either $B$ or $B'$: $$\begin{aligned}
  B&=\{q\in Y\cap(y',y-D)\mid\mbox{ there exists }p\in X\cap[x,\infty)\mbox{ with }(p,q)\in\C\},\\
  B'&=\{q\in Y\cap(y'+D,y)\mid\mbox{ there exists }p\in X\cap[x,\infty)\mbox{ with }(p,q)\in\C\}.
  \end{aligned}$$

![The no double crossing case is shown. The sets $A$ and $B$ are subsets of the top and bottom thick, blue intervals respectively.[]{data-label="fig:ub"}](ub.pdf)

We now argue it suffices to study only the following three cases. If either $A\neq\emptyset$ or $A'\neq\emptyset$, we can assume, without loss of generality, that $A\neq\emptyset$ and use Case (1) and Case (2). Now if we have $A=A'=\emptyset$ and either $B\neq\emptyset$ or $B'\neq\emptyset$, we can assume, without loss of generality, that $B\neq\emptyset$ and use Case (3). For each of these cases, we will choose a positive $\Delta\leq\frac{3D}{8}$ and show that $d_H(X,Y+\Delta)\leq\frac{D}{2}+\frac{\Delta}{3}$. As a result, $d_H(X,Y+\Delta)\leq\frac{D}{2}+\frac{D}{8}$.

We denote $p_0=\max{A}$ and $\eps=p_0-x-D$. We also let $q_0\in Y\cap[y',y]$ such that $(p_0,q_0)\in\C$; let $\eps'=(y-q_0)$. In this case, we choose $\Delta=\frac{3}{4}\eps$.\
We first observe that $(p_0-x')\geq(q_0-y')$. From the distortion of the pair $(x',y')$ and $(p_0,q_0)$, and noting that $(p_0-x')\geq(q_0-y')$, we get $$\begin{aligned}
  D\geq\mod{(p_0-x')-(q_0-y')}=(p_0-x')-(q_0-y')=\eps+\eps'.
  \end{aligned}$$

In particular, $\eps'\leq D$. Now from the distortion of the pair $(x,y)$ and $(p_0,q_0)$, we also get $$D\geq\mod{D+\eps-\eps'}=D+\eps-\eps'.$$ This implies that $\eps'\geq\eps$. Combining this with $\eps+\eps'\leq D$, we obtain $\eps\leq\frac{D}{2}$.\
In order to show $\overrightarrow{d}_H(X,Y+\Delta)\leq\frac{D}{2}+\frac{\Delta}{3}$, we consider the following partition of the real line into intervals: $$\begin{aligned}
  \I_1 &= \left(-\infty,q_0+\Delta-\frac{D}{2}\right],\;
  \I_2 = \left[q_0+\Delta-\frac{D}{2},q_0+\Delta+\frac{D}{2}\right],\\
  \I_3 &= \left[q_0+\Delta+\frac{D}{2},p_0\right], \mbox{ and }
  \I_4 = [p_0,\infty).
  \end{aligned}$$ For an arbitrary point $a\in X$ from any of the above intervals, we show that there exists a point $b\in Y$ such that $\mod{a-(b+\Delta)}\leq\left(\frac{D}{2}+\frac{\Delta}{3}\right)$.\
Let $a\in\I_1\cap X$ and $b\in Y$ such that $(a,b)\in\C$. From $\Delta<\eps\leq\eps'$, it follows that $a<x$. We first note that $(a,b)$ cannot cross $(x,y)$. If $a\in[x',x]$, then $(a,b)$ does not cross $(x,y)$ because of its distortion bound with the edge $(x',y')$. Now if $a<x'$, then $(a,b)$ does not cross $(x,y)$, otherwise $(a,b)$ would be a double crossing edge.

Now, we argue that $(a,b)$ cannot cross $(p_0,q_0)$ either. We assume the contrary that $(a,b)$ crosses $(p_0,q_0)$. Since $(a,b)$ does not cross $(x,y)$, we have $(b-q_0)\leq\eps'$. So, we get the following contradiction: $$\begin{aligned}
  D&\geq\bigmod{\mod{p_0-a}-\mod{q_0-b}}=\bigmod{\left[q_0+\eps'+\frac{D}{2}+\eps-a\right]-(b-q_0)}
  \geq\left(\frac{D}{2}-\Delta\right)+\eps'+\frac{D}{2}+\eps-\eps'\\
  &=D+\eps-\Delta>D.
  \end{aligned}$$

As a consequence if $b\leq a$, then it follows from the distortion of the pair $(a,b)$ and $(x,y)$ that $(a-b)\leq\frac{D}{2}$. If $b>a$, from the distortion of the pair $(a,b)$ and $(p_0,q_0)$ we get $b-a\leq\frac{D}{2}-(\eps+\eps')$. In either case, we conclude that $\mod{a-(b+\Delta)}\leq\frac{D}{2}$, since $\Delta<\eps$.\
For $a\in \I_2\cap X$ we have $\mod{a-(q_0+\Delta)}\leq\frac{D}{2}$.\
For $a\in \I_3\cap X$, the distance $\mod{a-(y+\Delta)}$ is maximized when $a$ is the right endpoint of the interval $\I_3$. Therefore, $$\mod{a-(y+\Delta)}\leq\bigmod{p_0-(y+\Delta)}=\max\left\{\bigmod{\frac{D}{2}-\eps'},\frac{D}{2}+\eps-\Delta\right\}=\frac{D}{2}+\frac{\Delta}{3}.$$\
If $(a,b)\in\C$ with $a\in \I_4\cap X$, we have $a>p_0=\max{A}$. Therefore, $(a,b)$ does not cross $(x,y)$. Also, it cannot cross $(x',y')$ because of our assumption of no double crossing. By an argument similar to $\I_1$, we conclude $\mod{a-(b+\Delta)}\leq\frac{D}{2}$.\
In order to show $\overrightarrow{d_H}(Y+\Delta,X)\leq\frac{D}{2}+\frac{\Delta}{3}$, we consider the following partition of the real line into intervals: $$\begin{aligned}
  \J_1 &= \left(-\infty,x-\frac{D}{2}-\Delta\right],
  \J_2 = \left[x-\frac{D}{2}-\Delta,y-\frac{\eps}{2}\right],
  \J_3 = \left[y-\frac{\eps}{2},y\right],\\
  \J_4 &= [y,p_0+\frac{D}{2}-\Delta],\mbox{ and }
  \J_5 = (p_0+\frac{D}{2}-\Delta,\infty).
  \end{aligned}$$ For an arbitrary point $b\in Y$ from any of the above intervals, we now show that there exists a point $a$ in $X$ such that $\mod{a-b}\leq\left(\frac{D}{2}+\frac{\Delta}{3}\right)$.\
Since $B=\emptyset$, for any $b\in \J_1\cap Y$ with edge $(a,b)\in\C$, the edge cannot cross $(x,y)$ or $(p_0,q_0)$. Therefore, $\mod{a-(b+\Delta)}\leq\frac{D}{2}$ as before.\
For $b\in \J_2\cap Y$, the distance $\mod{x-(b+\Delta)}$ is maximum at the endpoints of $\J_2$. Therefore, $$\begin{aligned}
    \mod{x-(b+\Delta)}
    \leq\max\left\{\frac{D}{2},\bigmod{x-y+\frac{\eps}{2}-\Delta}\right\}
    &=\max\left\{\frac{D}{2},\bigmod{-\frac{D}{2}+\frac{2\Delta}{3}-\Delta}\right\}\\
    &=\frac{D}{2}+\frac{\Delta}{3}.
  \end{aligned}$$\
Now, let $b\in \J_3\cap Y$ and $(a,b)\in\C$. Because of the distortion bound $D$ with the edges $(x,y)$ and $(p_0,q_0)$, a moment’s reflection reveals that $a\in\left(p_0-D-\frac{\eps}{2},x+D+\frac{\eps}{2}\right)=\left(x+\frac{\eps}{2},p_0-\frac{\eps}{2}\right)$. So, the distance $\mod{a-(b+\Delta)}$ is maximum when $b$ in one of the endpoints of $\J_3$ and $a$ the other endpoint of the interval $\left(x+\frac{\eps}{2},p_0-\frac{\eps}{2}\right)$. Therefore, $$\begin{aligned}
    \mod{a-(b+\Delta)}
    &\leq \max\left\{\bigmod{\left(x+\frac{\eps}{2}\right)-\left(y-\frac{\eps}{2}+\Delta\right)},\bigmod{\left(p_0-\frac{\eps}{2}\right)-(y+\Delta)}\right\}\\
   &=\max\left\{\frac{D}{2}-\frac{\Delta}{3},\frac{D}{2}+\frac{\Delta}{3}\right\}
   =\frac{D}{2}+\frac{\Delta}{3}.
  \end{aligned}$$\
For $b\in\J_4\cap Y$, the distance $\mod{p_0-(b+\Delta)}$ is maximum when $b$ is one of the endpoints of the interval $\J_4$. So, $$\mod{p_0,(b+\Delta)}\leq\max\left\{\bigmod{p_0-\left(y+\Delta\right)},\frac{D}{2}\right\}=\max\left\{\frac{D}{2}+\eps-\Delta,\frac{D}{2}\right\}=\frac{D}{2}+\frac{\Delta}{3}.$$\
Similarly, for $b\in\J_5\cap Y$, an edge $(a,b)\in\C$ cannot cross $(p_0,q_0)$ because of the distortion bound. Following the argument for $\I_1$, we conclude $\mod{a-(b+\Delta)}\leq\frac{D}{2}+\frac{\Delta}{3}$.

We denote $q_1=\min{B}$ and $\eta=y-D-q_1$. We also let $p_1\in Y\cap(x,\infty)$ such that $(p_1,q_1)\in\C$ and $\eta'=p_1-x$. We show, in this case, that $d_H(X,Y+\Delta)\leq\frac{D}{2}+\frac{\Delta}{3}$ for $\Delta=\frac{3}{4}\eta$. In this case, we choose $\Delta=\frac{3}{4}\eta$.\
We first observe that $(p_1-x')\geq(q_1-y')$. Therefore, from the distortion of the pair $(x',y')$ and $(p_1,q_1)$ we get $$\begin{aligned}
  D&\geq\mod{(p_1-x')-(q_1-y')}=(p_1-x')-(q_1-y'),\mbox{ since }(p_1-x')\geq(q_1-y')\\
  &=\left[(x-x')+\eta'\right]-\left[\frac{D}{2}+(x-x')-\frac{D}{2}-\eta\right]=\eta'+\eta.    
  \end{aligned}$$

In particular, $\eta'\leq D$. Now from the distortion of the pair $(x,y)$ and $(p_1,q_1)$, we also get $$D\geq\mod{D+\eta-\eta'}=D+\eta-\eta'.$$ This implies that $\eta'\geq\eta$. Combining this with $\eta+\eta'\leq D$, we get $\eta\leq\frac{D}{2}$.\
In order to show $\overrightarrow{d_H}(X,Y+\Delta)\leq\frac{D}{2}+\frac{\Delta}{3}$, we consider the following intervals of the real line: $$\begin{aligned}
  \I_1 &=\left(-\infty,q_1+\Delta-\frac{D}{2}\right],
  \I_2 =\left[q_1+\Delta-\frac{D}{2},x\right]
  \I_3 =\left[x,x+\frac{\eta}{2}\right]\\
  \I_4 &=\left[x+\frac{\eta}{2},y+\Delta-\frac{D}{2}\right],\mbox{ and }
  \I_5 =\left[y+\Delta-\frac{D}{2},\infty\right)
  \end{aligned}$$ By the symmetry of the problem, we follow the arguments presented in Case (1) for $\J_5,\J_4,\J_3,\J_2,\J_1$ to conclude the same about the nearest neighbor distances for $\I_1,\I_2,\I_3,\I_4,\I_5$ respectively.\
Now, in order to show $\overrightarrow{d_H}(Y+\Delta,X)\leq\frac{D}{2}+\frac{\Delta}{3}$, we consider the following intervals: $$\begin{aligned}
  \J_1 &= \left(-\infty,q_1\right),
  \J_2 = \left[q_1,p_1-\frac{D}{2}-\Delta\right],\\
  \J_3 &= \left[p_1-\frac{D}{2}-\Delta,p_1+\frac{D}{2}-\Delta\right],\mbox{ and }
  \J_4 = \left[p_1+\frac{D}{2}-\Delta,\infty\right).\\
  \end{aligned}$$ Again by the symmetry of the problem, we follow the arguments presented in Case (1) for $\I_4,\I_3,\I_2,\I_1$ to conclude the same about the nearest neighbor distances for $\J_1,\J_2,\J_3,\J_4$ respectively.

In this case, we take $\Delta=\frac{3}{4}\max\{\eps,\eta\}$ and consider all the intervals from Case (1) and Case (2) to conclude that $d_H(X,Y+\Delta)\leq\frac{D}{2}+\frac{\Delta}{3}$.

Now, we undertake the task of finding a suitable isometry/alignment when there is a double crossing in $\C$. In this case, we may have to consider flipping $Y$ to construct such an isometry. We always flip $Y$ about the midpoint of $x$ and $x'$ and denote the image by $\widetilde{Y}$. We first present two technical lemmas.

\[lem:cross\] Let $(p,q)\in\C$ be a double crossing; see . If we denote $h=(x-x')$, $\eps_1=(p-x)$, and $\eps_2=(y'-q)$, then we have the following:

i)  $\eps_1-\eps_2\geq h$,

ii) $\eps_1-\eps_2\leq D-h$,

iii) $h\leq\frac{D}{2}$, and

iv) $\mod{p-\widetilde q}\leq\frac{D}{2}-h$, where $\widetilde{q}$ denotes the reflection of $q$ about the midpoint of $x$ and $x'$.

![A double crossing $(p,q)$ is shown.[]{data-label="fig:cross"}](cross.pdf)

i)  Let us assume the contrary, i.e., $\eps_1<\eps_2+h$. Then, the distortion for the pairs $(x,y)$ and $(p,q)$ becomes $$\mod{\eps_2+D+h-\eps_1}=\eps_2+h+D-\eps_1> D.$$ This contradicts the fact that the distortion of $\C$ is $D$. Therefore, we conclude that $\eps_1-\eps_2\geq h$.

ii) Since from (i) we have $\eps_1\geq\eps_2$, from the distortion for the pairs $(p,q)$ and $(x',y')$, we have $$h+\eps_1-\eps_2\leq D$$ So, $\eps_1-\eps_2\leq D-h$.

iii) From (ii) we have $\eps_2+D\geq\eps_1$. Hence, the distortion for the pairs $(p,q)$ and $(x,y)$ implies $$\eps_2+D+h-\eps_1\leq D.$$ Adding (1) and (2), we get $2h\leq D$. Hence, $h\leq\frac{D}{2}$.

iv) If $p>\widetilde q$, then $$p-\widetilde q=\eps_1-\frac{D}{2}-\eps_2\leq(D-h)-\frac{D}{2}-\eps_2\leq\frac{D}{2}-h.$$ Otherwise, $$\widetilde q-p=\frac{D}{2}+\eps_2-\eps_1\leq\frac{D}{2}-(\eps_1-\eps_2)\leq\frac{D}{2}-h.$$ Therefore, $\mod{p-\widetilde q}\leq\frac{D}{2}-h$.

In our pursuit of constructing the right isometry, we first define a wide (double) crossing. We show in , that we need to flip $Y$ in the presence of such a wide crossing.

A crossing edge $(p,q)\in\C$ is called a *wide crossing* if either $p$ or $q$ lie outside $(x'-D,x+D)$; see .

Before presenting , we make an important observation first in the following technical lemma.

\[lem:wide-cross\] Let there be a wide crossing $(p,q)\in\C$ and an edge $(p_0,q_0)\in\C$ such that $p_0>x+D$ and $y'<q_0<y$. If we denote $\eps=p_0-x-D$, $\eps'=y-q_0$ and $h=x-x'$, then we have $\eps'\geq h$.

We prove by contradiction. Let us assume that $\eps'<h$. In , we have shown two possible positions of $p$. In each of the following cases, we arrive at a contradiction.

![A wide crossing $(p,q)$ is shown. Both the cases are shown in bright red.[]{data-label="fig:wide-cross"}](wide-cross.pdf)

From the distortion of the pair $(p,q)$ and $(p_0,q_0)$, we have $$\mod{(\eps_1+h+D+\eps)-(\eps'+\eps_2)}\leq D.$$ Since by assumption $h>\eps'$ and from we have $\eps_1\geq\eps_2$, we get $$\eps'\geq h+(\eps_1-\eps_2)+\eps\geq2h+\eps>h.$$

From the distortion of the pair $(p,q)$ and $(p_0,q_0)$, we get $$\mod{(\eps_2+D+h-\eps')-(\eps_1-D-\eps)}\leq D.$$ Since $D-(\eps_1-\eps_2)\geq h$ and $h>\eps'$, we have $$\eps'\geq D+h-(\eps_1-\eps_2)+\eps\geq2h+\eps>h.$$

Again from the distortion of the pair $(p,q)$ and $(p_0,q_0)$, we get $$\eps_2+\frac{D}{2}+h+\left(\frac{D}{2}-h\right)-\eps\leq D.$$ We get $\eps_2\leq\eps$. So, $\eps'\geq\eps\geq\eps_2\geq\eps_1+h-D\geq h$.

Therefore, $\eps'\geq h$.

\[thm:wide-cross\] Let $\C$ be a correspondence between two compact sets $X,Y\subseteq\R^1$ with distortion $D$. If there is a wide crossing $(p,q)\in\C$, then there exists a value $\Delta\in\R$ such that $$d_{H}(X,\widetilde{Y}+\Delta)\leq\frac{5}{8}D,$$ where $\widetilde{Y}$ denotes the refelection of $Y$ about the midpoint of $x$ and $x'$.

We first note from that $h=x-x'\leq\frac{D}{2},\mod{p-\widetilde q}\leq\left(\frac{D}{2}-h\right)$.

Let us define $$A=\{p\in X\cap(x+D,\infty)\mid\mbox{ there exists }q\in Y\cap[y',y]\mbox{ with }(p,q)\in\C\},$$ and $$A'=\{p\in X\cap(-\infty,x'-D)\mid\mbox{ there exists }q\in Y\cap[y',y]\mbox{ with }(p,q)\in\C\}.$$

![The correspondence with a wide crossing is shown. The sets $A$ and $B$ are subsets of the thick, dark blue regions on top and bottom respectively. In the bottom, we show the configuration when $Y$ is flipped about the midpoint of $x$ and $x'$.[]{data-label="fig:ub-1"}](ub-1.pdf "fig:") ![The correspondence with a wide crossing is shown. The sets $A$ and $B$ are subsets of the thick, dark blue regions on top and bottom respectively. In the bottom, we show the configuration when $Y$ is flipped about the midpoint of $x$ and $x'$.[]{data-label="fig:ub-1"}](ub-1-flip.pdf "fig:")

Let $p_0=\max A$ and $\eps=p_0-x-D$. We now define $$B=\{q\in Y\cap[y,\infty)\mid\mbox{ there exists }p\in X\cap[x,\infty)\mbox{ with }(p,q)\in\C\}.$$ Let us also define $q_1=\max B$, $\eta=q_1-y$, and let there exists edge $(p_1,q_1)\in\C$ with $\eta'=p_1-x$. Comparing with the edge $(x,y)$, we get $\eta'\geq\eta$. Because of the distortion bound with the wide crossing edge, we must have $\eta\leq\frac{D}{2}$. From , we also have $\eps'=(y-q_0)\geq h$.

If we take $\Delta=\frac{3}{4}\max\{\eps,\eta\}$, we argue that $$d_H(X,\widetilde{Y}+\Delta)\leq\frac{D}{2}+\frac{\Delta}{3}.$$

In order to show that $\overrightarrow{d}_H(X,\widetilde{Y}+\Delta)\leq\frac{D}{2}+\frac{\Delta}{3}$, we define the following intervals: $$\begin{aligned}
  \I_1 &= \left(-\infty,\widetilde{q_1}+\Delta-\frac{D}{2}\right]
  \I_2 = \left[\widetilde{q_1}+\Delta-\frac{D}{2},x'\right]
  \I_3 = \left[x',\widetilde{q_0}+\Delta+\frac{D}{2}\right],\\
  \I_4 &= \left[\widetilde{q_0}+\Delta+\frac{D}{2},p_0\right],\mbox{ and }
  \I_5 = [p_0,\infty).
  \end{aligned}$$

For $a\in(\I_1\cup\I_5)\cap X$ and an edge $(a,b)\in\C$, the edge has to be a double crossing edge because of the distortion bound with the wide crossing edge. So after the flip, the edge $(a,\widetilde{b})$ does not cross $(p_0,\widetilde{q_0})$ or $(p_1,\widetilde{q_1})$. As a result, when $a\geq\widetilde{b}$, we have $(a-\widetilde{b})\leq\left(\frac{D}{2}-h\right)$ as shown in and $(\widetilde{b}-a)\leq\left(\frac{D}{2}-\max\{\eps,\eta\}\right)$ otherwise. Therefore, $\mod{a-(\widetilde{b}+\Delta)}\leq\frac{D}{2}$.\
For $a\in\I_2\cap X$ we have $$\mod{a-(\widetilde{q_1}+\Delta)}\leq\max\left\{\frac{D}{2},\mod{x'-\widetilde{q_1}-\Delta}\right\}=\max\left\{\frac{D}{2},\bigmod{\frac{D}{2}+\eta-\Delta}\right\}\leq\frac{D}{2}+\frac{\Delta}{3}.$$

For $a\in\I_3\cap X$ we have $$\mod{a-(\widetilde{q_0}+\Delta)}
 \leq\max\left\{\mod{x'-\widetilde{q_0}-\Delta},\frac{D}{2}\right\}
 \leq\max\left\{\bigmod{\eps'-\frac{D}{2}},\frac{D}{2}\right\}\leq\frac{D}{2}$$

For $a\in\I_4\cap X$ we have $$\begin{aligned}
 \mod{a-(\widetilde{y'}+\Delta)}
 &\leq\max\left\{\bigmod{\widetilde{q_0}+\frac{D}{2}-\widetilde{y'}},\bigmod{p_0-\widetilde{y'}-\Delta}\right\}
 =\max\left\{\bigmod{\frac{D}{2}-(D+h-\eps')},\bigmod{\frac{D}{2}+\eps-\Delta}\right\}\\
 &=\max\left\{\bigmod{\frac{D}{2}-(\eps'-h)},\bigmod{\frac{D}{2}+\frac{\Delta}{3}}\right\}
 \leq\frac{D}{2}+\frac{\Delta}{3}.
 \end{aligned}$$

In order to show that $\overrightarrow{d}_H(\widetilde{Y}+\Delta,X)\leq\frac{D}{2}+\frac{\Delta}{3}$, we define the following intervals: $$\begin{aligned}
  \J_1 &= \left(-\infty,\widetilde{q_1}\right],\;
  \J_2 = \left[\widetilde{q_1},x'+\frac{D}{2}-\Delta\right],\;
  \J_3 = \left[x'+\frac{D}{2}-\Delta,\widetilde{y'}-\frac{2\Delta}{3}\right],\\
  \J_4 &= \left[\widetilde{y'}-\frac{2\Delta}{3},\widetilde{y'}\right],\;
  \J_5 = \left[\widetilde{y'},p_0+\frac{D}{2}-\Delta\right],\mbox{ and }
  \J_6 = \left[p_0+\frac{D}{2}-\Delta,\infty\right).
  \end{aligned}$$

For $\J_1$, $\J_2$, $\J_4$, $\J_5$, and $\J_6$ we use routine arguments used in Case (1) of . As a new situation, we only consider $\J_3$ here. For $b\in\J_3\cap Y$ we have $$\begin{aligned}
  \mod{x-(b+\Delta)}\leq\max\left\{\bigmod{x-x'-\frac{D}{2}},\bigmod{x-\widetilde{y'}+\frac{2\Delta}{3}-\Delta}\right\}
 \leq\max\left\{\bigmod{\frac{D}{2}-h},\bigmod{\frac{D}{2}+\frac{\Delta}{3}}\right\}\leq\frac{D}{2}+\frac{\Delta}{3}.
 \end{aligned}$$

In this case, we assume, without loss of generality, that $\eta_1\leq\eta_2$; see . When considering $\widetilde{Y}$, we first note from the distortion bound with $(p,\widetilde{q})$ that $\eta_1,\eta_2\leq\left(\frac{D}{2}-h\right)$.\
If $h>\frac{3D}{8}$, then $\eta_1>\frac{D}{8}$. We take $\Delta=\left(\eta_1-\eta_2'-\frac{D}{8}\right)$, and we argue that $$d_H(X,\widetilde{Y}+\Delta)\leq\frac{D}{2}+\frac{D}{8}.$$

![Wide crossing exists, and both $A=\emptyset$, $A'=\emptyset$[]{data-label="fig:ub1"}](ub-2.pdf "fig:") ![Wide crossing exists, and both $A=\emptyset$, $A'=\emptyset$[]{data-label="fig:ub1"}](ub-2-flip.pdf "fig:")

In order to show that $\overrightarrow{d}_H(X,\widetilde{Y}+\Delta)\leq\frac{D}{2}+\frac{D}{8}$, we define the following intervals: $$\begin{aligned}
  \I_1 &= \left(-\infty,\widetilde{q_1}+\Delta-\frac{D}{2}\right],
  \I_2 = \left[\widetilde{q_1}+\Delta-\frac{D}{2},x'\right],
  \I_3 = \left[x',x'+\frac{D}{8}+\Delta\right],\\
  \I_4 &= \left[x'+\frac{D}{8}+\Delta,x-\frac{D}{8}+\Delta\right],
  \I_5 = \left[x-\frac{D}{8}+\Delta,\widetilde{y'}-\frac{5D}{8}+\Delta\right],\mbox{ and }
  \I_5 = \left[\widetilde{y'}+\Delta+\frac{D}{2},\infty\right).
  \end{aligned}$$\
For $\I_1$ and $\I_5$, we use the arguments from Case (1).\
For $a\in\I_2\cap X$, we get $$\begin{aligned}
  \mod{a-(\widetilde{q_1}+\Delta)}\leq\max\left\{\frac{D}{2},x'-\widetilde{q_1}-\Delta\right\}
  =\max\left\{\frac{D}{2},\frac{D}{2}+\eta_1-\Delta\right\}
  &=\max\left\{\frac{D}{2},\frac{D}{2}+\eta_1-\eta_1+\frac{D}{8}\right\}\\
  &=\frac{D}{2}+\frac{D}{8}.    
  \end{aligned}$$ A similar argument holds also for $\I_3,\I_5$.\
For $a\in\I_4\cap X$, let $b\in[y',y]\cap Y$ such that $(a,b)\in\C$. If $a\geq b$, then by the distortion bound with $(x,y)$ we have $(a-x')\leq(b-y')$. So, $$\begin{aligned}
 \mod{(\widetilde{b}+\Delta)-a}&=\Delta+\frac{D}{2}+h-(a-x')-(b-y')
 \leq\Delta+\frac{D}{2}+h-2(a-x')\\
 &\leq\Delta+\frac{D}{2}+h-2\left(\frac{D}{8}+\Delta\right)
 =\frac{D}{2}+h-\frac{D}{4}-\Delta
 =\frac{D}{2}+h-\frac{D}{4}\\
 &\leq\frac{D}{2}+\frac{3D}{8}-\frac{D}{4}
 =\frac{D}{2}+\frac{D}{8}.
 \end{aligned}$$ If $a\leq b$, we argue by symmetry that $\mod{(\widetilde{b}+\Delta)-a}\leq\frac{D}{2}+\frac{D}{8}$.\
In order to show that $\overrightarrow{d}_H(\widetilde{Y}+\Delta,X)\leq\frac{D}{2}+\frac{D}{8}$, we define the following intervals: $$\begin{aligned}
  \J_1 &= \left(-\infty,\widetilde{q_1}\right],
  \J_2 = \left[\widetilde{q_1},x'\right],
  \J_3 = \left[x',x'+\frac{D}{2}-\Delta\right]\\
  \J_4 &= \left[x'+\frac{D}{2}-\Delta,x+\frac{D}{2}-\Delta\right],
  \J_5 = \left[x+\frac{D}{2}-\Delta,\widetilde{q_2}\right],\mbox{ and }
  \J_6 = \left[\widetilde{q_2},\infty\right).
  \end{aligned}$$ The analysis for $\I_1,\I_2,\I_3,\I_4$ are similar to Case (1). We note for $\J_5$ that $\mod{(\widetilde{q_2}+\Delta)-p_1}
  =\frac{D}{2}+\eta_2-\eta_1'+\Delta\leq\frac{D}{2}+\eta_2'-\eta_1+\Delta
  =\frac{D}{2}+\eta_2'-\eta_1+\left(\eta_1-\eta_2'-\frac{D}{8}\right)\leq\frac{D}{2}$.\
If $h\leq\frac{3D}{8}$, then $\eta_1\geq\frac{D}{8}$. We take $\Delta=\left(\frac{D}{8}-\eta_1\right)$, and we argue that $$d_H(X,\widetilde{Y}+\Delta)\leq\frac{D}{2}+\frac{D}{8}.$$ We use the same intervals as Case (1). With this new $\Delta$, the only changes in the calculations appear in $\I_3$. We show $\I_3$ here.\
$$\begin{aligned}
 \mod{(\widetilde{b}+\Delta)-a}&=\Delta+\frac{D}{2}+h-(a-x')-(b-y')
 \leq\Delta+\frac{D}{2}+h-2(a-x')\\
 &\leq\Delta+\frac{D}{2}+h-2\left(\frac{D}{8}+\Delta\right)
 =\frac{D}{2}+h-\frac{D}{4}-\Delta
 =\frac{D}{2}+h-\frac{D}{4}-\left(\frac{D}{8}-\eta_1\right)\\
 &\leq\frac{D}{2}+h-\frac{3D}{8}+\eta_1
 \leq\frac{D}{2}+h-\frac{3D}{8}+\left(\frac{D}{2}-h\right)
 =\frac{D}{2}+\frac{D}{8}.
 \end{aligned}$$

This completes the proof for wide crossing.

In order to complete our analysis of various types of correspondences, we show now that a flip is not required if there is no wide crossing in $\C$.

\[thm:no-wide\] Let $\C$ be a correspondence between two compact sets $X,Y\subset\R^1$ with distortion $D$. If there are double crossings but not wide, then there exists a value $\Delta\in\R$ such that $$d_H(X,Y+\Delta)\leq\frac{D}{2}+\frac{D}{8}.$$

We assume that there are double crossings in $\C$, but none of them are wide; see .

![No wide crossing exists[]{data-label="fig:cross-1"}](cross-1.pdf)

This case is similar to Case (1) and Case (3) of .

If $\eta_1\geq\eps$, then we note that $d_H(X,Y)\leq\frac{D}{2}$. This is the trivial case. So, we assume that $\eta_1<\eps$.

From the distortion of the pair $(p_0,q_0)$ and $(p_2,q_2)$, we have $$D\geq(\eta_2+h+D+\eps)-(\eta_1+\eps').$$ So, we get $\eta_2+\eps+h\leq\eta_1+\eps'$.

We take $\Delta=\eps-\eta_1$. We first consider the following intervals: $$\begin{aligned}
  \I_1 &= \left(-\infty,y'+\Delta-\frac{D}{2}\right], 
  \I_2 = \left[y'+\Delta-\frac{D}{2},x'\right]
  \I_3 = [x',x],\\ 
  \I_4 &= \left[x,q_0+\frac{D}{2}+\Delta\right], 
  \I_5 = \left[q_0+\frac{D}{2}+\Delta,p_0\right], 
  \mbox{ and }\I_6 = [p_0,\infty).\end{aligned}$$ The intervals similar to $\I_2,\I_3,\I_4,\I_5$ are considered already in . We show that if $p_2\in\I_1\cap X$, then any edge $(p_2,q_2)\in\C$ cannot cross $(x',y')$, consequently $\mod{p_2-(q_2+\Delta)}\leq\frac{D}{2}$. If we assume the contrary, then the edge has to be a double crossing; see . Since $p_2$ is assumed to be in $\I_1$, we have $\left(\eta_2-\frac{D}{2}\right)>\left(\frac{D}{2}-\Delta\right)$. This would imply $$\eta_2>D-\Delta=D-(\eta_1-\eps)\geq D+\eta_2+h-\eps'=h+\eta_2+(D-\eps')\geq h+\eta_2.$$ This is a contradiction. Therefore, $\overrightarrow{d}_H(X,Y+\Delta)\leq\frac{D}{2}$.

For $\overrightarrow{d}_H(Y+\Delta,X)$, the arguments are similar to .

In this case, we choose $\Delta=\frac{3}{4}\max\{\eta_1,\eps_2\}$ and conclude the result using arguments similar to Case (2) in .

This concludes the proof.

We conclude this section by showing in that the bound of is a tight upper bound in the following sense:

\[thm:lb\] For any $0<\eps<\frac{1}{4}$ and $\delta>0$, there exist compact $X,Y\subset\R$ with $d_{GH}(X,Y)=\delta$ and $$d_{H,iso}(X,Y)=\left(\frac{5}{4}-\eps\right)\delta.$$

It suffices to assume that $\eps=\frac{1}{4(2k+1)}$ for some $k\in\mathbb{N}$. We now take (sorted) $$X=\{x',x,x_k,x_{k-1},\cdots,x_1,x_0\}\mbox{ and }Y=\{y',y_0,y_1,\cdots,y_{k-1},y_k,y\},$$ with distances as shown in . As a result, we also have $(y_i-x) =4i\eps\delta$ and $(x_k-y_i)=2\delta+4(k-i+1)\eps\delta$, $\forall i\in\{0,1,2,\cdots,k\}$.

![This picture demonstrates the configuration of $X$ and $Y$. The correspondence $\C$ is shown using the (red) edges. In the bottom, $X$ and $\widetilde{Y}$, the reflection of $Y$ about the midpoint of $x$ and $x'$, are shown, along with the correspondence $\C$ by the red edges.[]{data-label="fig:lb"}](lb.pdf "fig:") ![This picture demonstrates the configuration of $X$ and $Y$. The correspondence $\C$ is shown using the (red) edges. In the bottom, $X$ and $\widetilde{Y}$, the reflection of $Y$ about the midpoint of $x$ and $x'$, are shown, along with the correspondence $\C$ by the red edges.[]{data-label="fig:lb"}](lb-flip.pdf "fig:")

To prove our claim that $d_{H,iso}(X,Y)=\left(\frac{5}{4}-\eps\right)\delta$, we consider translating both $Y$ and $\widetilde{Y}$, the reflection of $Y$ about the midpoint of $x$ and $x'$.

When translating $\widetilde{Y}$, we note that the smallest Hausdorff distance of $\frac{3\delta}{2}$ is achieved for a translation of $\widetilde{Y}$ by an amount of $\frac{\delta}{2}$ to the right. For this amount of translation, $\widetilde{y'}$ becomes the midpoint of $x$ and $x_0$, where $\widetilde{y'}$ is the reflection of $y'$ about the midpoint of $x$ and $x'$. And, all the other points of $\widetilde{Y}$ are at distance at least $50\delta$ from $x$.

Now, we consider translating $Y$ by an amount $\Delta\in\R$. We first observe that $d_H(X,Y)=2\delta$, and the distance is attained by $x_0$ and $y$. Now, a translation of $Y$ to the left is only going to increase the Hausdorff distance $d_H(X,Y+\Delta)$. Taking this argument one step further we get the following analysis as we vary $\Delta$:

If $\Delta\in\left(-\infty,\frac{3\delta}{4}+\eps\delta\right)$, then the pair $(x_0,y)$ gives $$d_H(X,Y+\Delta)=2\delta-\Delta>2\delta-\frac{3\delta}{4}-\eps\delta=\left(\frac{5}{4}-\eps\right)\delta.$$ For $\Delta=\frac{3\delta}{4}+\eps\delta$, we get $x_0-(y+\Delta)=\left(\frac{5}{4}-\eps\right)\delta$. Also, $y_k+\Delta-x=\left(\frac{5}{4}-\eps\right)\delta$ and $x_k-(y_k+\Delta)=\left(\frac{5}{4}-\eps\right)\delta+4\eps\delta$. So, $d_H(X,Y+\Delta)=\left(\frac{5}{4}-\eps\right)\delta$, which is attained by $\mod{x_0-y_k}$.

Following this pattern, we conclude that $d_H(X,Y+\Delta)>\left(\frac{5}{4}-\eps\right)\delta$, except for $\Delta=\frac{3\delta}{4}+\eps\delta+4i\eps\delta$ for $i\in\{0,1,2,\cdots,k\}$. Therefore, $d_{H,iso}(X,Y)=\left(\frac{5}{4}-\eps\right)\delta$. We summarize our analysis in .

                                                  $\Delta$                                                 $\overrightarrow{d}_H(X,Y+\Delta)$   $\overrightarrow{d}_H(Y+\Delta,X)$              $d_H(X,Y+\Delta)$
  -------------------------------------------------------------------------------------------------------- ------------------------------------ ------------------------------------ ----------------------------------------
                            $\left(-\infty,\frac{3\delta}{4}+\eps\delta\right)$                            $(x_0,y)$                            –                                     $>\left(\frac{5}{4}-\eps\right)\delta$
                                       $\frac{3\delta}{4}+\eps\delta$                                      $(x_0,y)$                            $(y_k,x),(y,x_k)$                     $\left(\frac{5}{4}-\eps\right)\delta$
            $\left(\frac{3\delta}{4}+\eps\delta,\frac{3\delta}{4}+\eps\delta+4\eps\delta\right)$           –                                    $(y_k,x),(y_k,x_k)$                   $>\left(\frac{5}{4}-\eps\right)\delta$
                                 $\frac{3\delta}{4}+\eps\delta+4\eps\delta$                                –                                    $(y_{k-1},x),(y_k,x_k)$               $\left(\frac{5}{4}-\eps\right)\delta$
                                                  $\cdots$                                                 $\cdots$                             $\cdots$                                             $\cdots$
   $\left(\frac{3\delta}{4}+\eps\delta+4i\eps\delta,\frac{3\delta}{4}+\eps\delta+4(i+1)\eps\delta\right)$  –                                    $(y_{k-i},x),(y_{k-i},x_k)$           $>\left(\frac{5}{4}-\eps\right)\delta$
                              $\frac{3\delta}{4}+\eps\delta+4(i+1)\eps\delta$                              –                                    $(y_{k-i-1},x)$, $(y_{k-i},x_k)$      $\left(\frac{5}{4}-\eps\right)\delta$
                                                  $\cdots$                                                 $\cdots$                             $\cdots$                                             $\cdots$
                                $\frac{3\delta}{4}+\eps\delta+4k\eps\delta$                                $(x,y_0)$                            $(y_0,x)$                                   $(\frac{5}{4}-\eps)\delta$
                      $\left(\frac{3\delta}{4}+\eps\delta+4k\eps\delta,\infty\right)$                      $(x,y_0)$                            –                                     $>\left(\frac{5}{4}-\eps\right)\delta$

  : A summary of $d_H(X,Y+\Delta)$ is recorded for $\Delta\in\R$. In the second and third columns, the directed Hausdorff distances are achieved for the shown pairs of points. The other columns are self-explanatory.[]{data-label="tab:lb"}

With the $d_{H,iso}(X,Y)$ computed, we now define the following correspondence $\C$ between $X$ and $Y$: $$\C=\big\{(x_i,y_i)\mid i\in\{0,1,\cdots,k\}\big\}\cup\big\{(x',y'),(x,y)\big\}.$$ The distortion of $\C$ is evidently $2\delta$. Moreover, we observe that $\C$ is an optimal correspondence. Therefore, $d_{GH}(X,Y)=\delta$.

Conclusions and Future Work
===========================

In this work, we focus on approximating Gromov-Hausdorff distance by the Hausdorff distance for subsets of $\R^1$. We believe that the problem of computing the Gromov-Hausdorff distance in the $\R^1$ case is NP-hard. The question of a polynomial time approximation algorithm for subsets of $\R^d$ is still open for $d\geq2$.

Acknowledgments
===============

The authors would like to thank Yusu Wang and Facundo Mémoli for hosting Sushovan Majhi at OSU and for discussions on the project during the visit. We also thank Helmut Alt for his valuable feedback during his visit at Tulane University in the Spring of 2019.

A Weak Upper Bound of 2
=======================

\[thm:2-ub\] For any two compact subsets $X,Y$ of $\R^1$, we have the following $$d_{H,iso}(X,Y)\leq 2d_{GH}(X,Y).$$

Let $C$ be any correspondence between two compact subsets $X,Y$ of $\R^1$. There exists a pair of relatives $(x,y),(x',y')\in C$ such that $\bigmod{\mod{x-x}-\mod{y-y'}}=D$, where $D$ is the distortion of $C$. Without loss of generality, we assume that $x\leq x'$ and $\mod{x-x'}\leq\mod{y-y'}$. Then, there exists an $R^1$-isometry such that, when applied on $Y$, the pairs look like . From now on, we assume this configuration for any given correspondence $C$.

It suffices to show that for any correspondence $\C\subseteq X\times Y$ with distortion $D$, there exists a Euclidean isometry $T\in\mathcal{E}(R^1)$ such that $$d_H(X,T(Y))\leq D.$$

![This standard alignment is assumed for $\C$ in this proof. We may need to apply a Euclidean isometry on $Y$ so that $(x_L,y_1)$ and $(x_R,y_2)$ do not cross and $x_L=y_1$.[]{data-label="fig:standard"}](standard.pdf)

Let us take an arbitrary correspondence $\C$ between $X$ and $Y$ with distortion $D$. Let us denote $x_L=\min{X}$ and $x_R=\max{X}$. We also assume that $(x_L,y_1),(x_R,y_2)\in C$ for some $y_1,y_2\in Y$.

Without loss of generality, we can assume that the edges $(x_L,y_1),(x_R,y_2)$ do not cross, i.e., $y_1\leq y_2$. This may require to flip $Y$ once, but applying such an isometry is distortion-safe. We can further assume that $x_L=y_1$, which may require an additional translation. See .

In this case, we claim that $d_H(X,Y)\leq D$. To see the claim, consider any edge $(p,q)\in\C$. Since, the edge does not cross $(x_L,y_1)$, we must have $\mod{p-q}\leq D$. So, $d_H(X,Y)\leq D$.

Let there at least an edge that crosses the edge $(x_L,y_1)$. We now let $$\eps_1=\max\{(x-x_L)\mid\text{the edge }(x,y)\in\C\text{ crosses
    }(x_L,y_1)\text{ for some }y\in Y\},$$ and

$$\eps_2=\max\{(y_1-y)\mid\text{the edge }(x,y)\in\C\text{ crosses
    }(x_L,y_1)\text{ for some }x\in X\}.$$ We first observe that $\eps_1,\eps_2>0$. In this case, we consider both $\eps_1,\eps_2\leq D$. We claim that $d_H(X,Y)\leq D$.

To see that $\overrightarrow{d_H}(X,Y)\leq D$, consider an $x\in X$. If $x\leq x_L+\eps_1$, then we have $\mod{x-y_1}\leq D$. And, we note that $(x.y)$ cannot cross $(x_L,y_1)$, hence we have $\mod{x-y}\leq D$.

Now to show that $\overrightarrow{d_H}(Y,X)\leq D$, we take an $y\in Y$. If $y<y_1$, then we have $\mod{y-x_L}\leq D$. If $y>y_1$, we consider $x\in X$ such that $(x,y)\in\C$. Then, $(x,y)$ does not cross $(x_L,y_1)$. Therefore, $\mod{x-y}\leq D$. This proves the claim.

The last case deals with the scenario of having at least one edge crossing the edge $(x_L,y_1)$ and either $\eps_1>D$ or $\eps_2>D$. In this case, we pick $T$ to be the translation of $\R^1$ to the right by $D$ and argue that $d_H(X,T(Y))\leq D$.

Since the edge $(x_R,y_2)$ does not cross $(x_L,y_1)$, we first note that $\mod{x_R-y_2}\leq D$. Therefore, $\eps_1+\eps_2\leq2D$.

To see that $\overrightarrow{d_H}(X,T(Y))\leq D$, consider an $x\in X$. If $x\leq x_L+\eps_1$, then we still have $\mod{x-(y_1+D)}\leq D$. If $x>x_L+\eps_1$, then consider $(x,y)\in\C$. The edge $(x,y)$ does not cross $(x_L,y_1)$, hence we have $\mod{x-y}\leq D$. Since $\eps_1+\eps_2>D$, we have $y\leq x$. Hence, $\mod{(y+D)-x}\leq D$.

Now to show that $\overrightarrow{d_H}(T(Y),X)\leq D$, we take an $y\in
    Y$. If $y<y_1$, then we have $\mod{y-x_L}\leq D$. If $y>y_1$, we consider $x\in X$ such that $(x,y)\in\C$. Then, $(x,y)$ does not cross $(x_L,y_1)$. Therefore, $\mod{x-y}\leq D$. This proves the claim.

[^1]: supported by the National Science Foundation grant CCF-1618469

[^2]: corresponding author `[email:smajhi@tulane.edu]`
