In this section we define the interleaving distance of Reeb graphs
due to de Silva, Munch, and Patel
(2016). Strictly speaking it
is somewhat misleading to name this the interleaving distance of
Reeb graphs because we are not comparing the Reeb graphs directly,
instead we compare what we name the Reeb precosheaf^{[3]}. de Silva, Munch, and Patel
(2016) discuss very
thoroughly, why we may do this and later they also translate this
into a more geometric comparison of Reeb graphs. We define this Reeb
precosheaf somewhat differently from the way it is defined in this
article. Using the notion of an intersection-based space we may say
that de Silva, Munch, and Patel
(2016) define the Reeb
precosheaf as a precosheaf on the intersection-based space, that has
the real numbers as an underlying set and the open intervals as
distinguished open subsets. We will use a different space, but all
of the distinguished open subsets of this space, except for three,
can be identified with an open interval. Now because precosheaves
are just functors on the distinguished open subsets, this is pretty
much the same data. And the reason we can’t identify all
distinguished open subsets with an interval is that we work with
\(\overline{{\mathbb{R}}}\) instead of \({\mathbb{R}}\), in some
sense \(\overline{{\mathbb{R}}}\) has three more open intervals than
\({\mathbb{R}}\). Now we begin with defining this intersection-based
space.

**Definition.**We define \(\overline{{\mathbb{R}}}_{\infty}\) to be the space that has \(\overline{{\mathbb{R}}}\) as an underlying set and \(\{\overline{{\mathbb{R}}}\} \cup \{(a, \infty] ~ | ~ a \in \overline{{\mathbb{R}}}\}\) as it’s intersection-base.Similarly we define \(\overline{{\mathbb{R}}}_{-\infty}\) to be the space with the same underlying set and \(\{\overline{{\mathbb{R}}}\} \cup \{[-\infty, b) ~ | ~ b \in \overline{{\mathbb{R}}}\}\) as it’s intersection-base.

Finally we set \({\overline{{\mathbb{E}}}}:= \overline{{\mathbb{R}}}_{\infty} \times \overline{{\mathbb{R}}}_{-\infty}\) and \(\overline{D} := {\{(x, y) \in {\overline{{\mathbb{E}}}}~|~ x \leq y\}}\).

We note that any functor from the category of topological spaces to the category of sets defines a precosheaf on any topological space \(X\), since we may equip any open subset \(U \subseteq X\) with the subspace topology and since inclusions of subsets are continuous with respect to this topology. In the following definition we define a functor on the category of topological spaces and in this way also a precosheaf on any topological space.

**Definition.**For topological space \(X\) we define \(\Lambda(X)\) to be the set of connected components of \(X\).For a continuous map \(\varphi \colon X \rightarrow Y\) we define \(\Lambda(\varphi)\) to be the induced map from \(\Lambda(X)\) to \(\Lambda(Y)\).

Now let \(f \colon X \rightarrow \overline{{\mathbb{R}}}\) and \(g \colon Y \rightarrow \overline{{\mathbb{R}}}\) be continuous functions, let \(\varphi \colon f \rightarrow g\) be a homomorphism in the category of \(\overline{{\mathbb{R}}}\)-spaces, and let \(\Delta \colon \overline{{\mathbb{R}}} \rightarrow \overline{D}, t \mapsto (t, t)\). For a distinguished open subset \(U \subseteq \overline{D}\) let \(\varphi |_{(\Delta \circ f)^{-1} (U)} \colon (\Delta \circ f)^{-1} (U) \rightarrow (\Delta \circ g)^{-1} (U)\) be the restriction of \(\varphi\) to \((\Delta \circ f)^{-1} (U)\).

**Definition**(Reeb Precosheaf)**.**We set \(\mathcal{C} f := (\Delta \circ f)_* \Lambda\) and name this the*Reeb precosheaf of \(f\)*.Moreover we define a homomorphism \(\mathcal{C} \varphi\) from \(\mathcal{C} f\) to \(\mathcal{C} g\). For a distinguished open subset \(U \subseteq \overline{D}\) we set \((\mathcal{C} \varphi)_U := \Lambda \big(\varphi |_{(\Delta \circ f)^{-1} (U)}\big)\).

With these definitions \(\mathcal{C}\) defines a functor from the
category of \(\overline{{\mathbb{R}}}\)-spaces to the category of
set-valued precosheaves on \(\overline{D}\). Now assume that \(g\)
is a constructible \(\overline{{\mathbb{R}}}\)-space^{[4]}. We discuss the relationship of the Reeb graph
\(\mathcal{R} g\) and the Reeb precosheaf \(\mathcal{C} g\).

**Lemma.**The homomorphism \((\mathcal{C} \circ \pi)_g\) from \(\mathcal{C} g\) to \(\mathcal{C} \mathcal{R} g\) is an isomorphism of precosheaves.

The previous lemma implies that the isomorphism class of \(\mathcal{C} g\) is determined by \(\mathcal{R} g\). Next we will see that the converse is also true.

**Lemma.**Let \(\beta \colon \mathcal{C} f \rightarrow \mathcal{C} g\) be a homomorphism of precosheaves, then there is a unique homomorphism \(\alpha \colon f \rightarrow \mathcal{R} g\) of \(\overline{{\mathbb{R}}}\)-spaces such that the diagram \[ \xymatrix@+=3pc{ \mathcal{C} f \ar[d]_{\mathcal{C} \alpha} \ar[dr]^{\beta} \\ \mathcal{C} \mathcal{R} g & \mathcal{C} g \ar[l]^{(\mathcal{C} \circ \pi)_g} } \] commutes.

*Remark.*One can rephrase the previous lemma in the terminology of category theory in the following way. The homomorphism \((\mathcal{C} \circ \pi)_g^{-1}\) yields a representation of the contravariant functor \({\operatorname{Hom}}(\mathcal{C} \_, \mathcal{C} g)\). A vast generalization of this statement has been provided by Funk (1995).

The previous two lemmata have the following

**Corollary.**The map \[\mathcal{C} (\_) \colon {\operatorname{Hom}}(f, \mathcal{R} g) \rightarrow {\operatorname{Hom}}(\mathcal{C} f, \mathcal{C} \mathcal{R} g), \alpha \mapsto \mathcal{C} \alpha\] is a bijection.*Proof.*First we note that the post-composition \((\mathcal{C} \circ \pi)_g^{-1} \circ (\_)\) yields a bijection from \({\operatorname{Hom}}(\mathcal{C} f, \mathcal{C} \mathcal{R} g)\) to \({\operatorname{Hom}}(\mathcal{C} f, \mathcal{C} g)\). Now the previous lemma states that the composition \((\mathcal{C} \circ \pi)_g^{-1} \circ \mathcal{C} (\_)\) is a bijection as well. Thus also \(\mathcal{C} (\_)\) is a bijection.

**Corollary.**The functor \(\mathcal{C}\) is full and faithful on the full subcategory of Reeb graphs of constructible \(\overline{{\mathbb{R}}}\)-spaces.

The previous corollary implies that the isomorphism class of \(\mathcal{R} g\) is determined by the isomorphism class of \(\mathcal{C} \mathcal{R} g\) and this class in turn is determined by \(\mathcal{C} g\), hence \(\mathcal{C} g\) determines the isomorphism class of \(\mathcal{R} g\).

In summary we may associate to any \(\overline{{\mathbb{R}}}\)-space a set-valued precosheaf, the Reeb precosheaf. In the following subsection we define two interleaving distances for set-valued precosheaves on \(\overline{D}\). And for constructible \(\overline{{\mathbb{R}}}\)-spaces we may also refer to the interleaving distances of the Reeb precosheaves as interleaving distances of Reeb graphs. This is justified by the fact that de Silva, Munch, and Patel (2016) also define an interleaving distance of Reeb graphs, that is equal to the interleaving distance of the Reeb precosheaves for constructible \(\overline{{\mathbb{R}}}\)-spaces.

^{[3] }
de Silva, Munch, and Patel
(2016) actually name it
the Reeb cosheaf, because in their setup, using locally
connected spaces, it always is a cosheaf, a precosheaf with
further properties.

^{[4] }
see the first
appendix for our definition of a constructible
\(\overline{{\mathbb{R}}}\)-space