# Properties of Frechet distance

There is an old construction, apparently due to Frechet's PhD thesis (which is unfortunately written in French and in ancient notation), which turns the set of curves in a metric space modulo reparametrizations into a metric space itself. The idea is that if $$f$$ and $$g$$ are curves in a metric space $$X$$ (meaning continuous maps from $$[0,1]$$ to $$X$$), then their distance is defined as $$d(f,g)\equiv \mathrm{Inf}_{\phi,\psi}\mathrm{Sup}_{t\in [0,1]} d(f(\phi(t)),g(\psi(t))),$$ where $$\phi$$ and $$\psi$$ are orientation-preserving homeomorphisms from $$[0,1]$$ to itself. Most of the properties of a distance follow trivially from the definition, but I am having some trouble showing that $$d(f,g)=0$$ implies that $$f$$ and $$g$$ differ only by a homeomorphism. Potentially we could merely have a sequence $$(\phi_n,\psi_n)$$ of homeomorphisms for which the the supremum converged to zero, but which did not converge to a pair of homeomorphisms $$(\phi,\psi)$$ for which it vanishes. Why must the infimum be realized? I believe it should be possible to show this using some kind of uniform convergence, and also possibly the compactness of $$[0,1]$$, but haven't succeeded. For my own purposes I am especially interested in whether or not it is necessary to use the compactness of $$[0,1]$$ (I am trying to understand to what extent $$[0,1]$$ can be generalized to an arbitrary topological space in this definition).

In fact it is not true in this generality: the simple counterexample, inspired by a famous Aesop's fable, is: $$X=\mathbb{R}$$, $$f(x)=x$$, and $$g(x)=\max(0, 2x-1)$$ for $$x\in I:=[0,1]$$. The Fréchet distance is clearly zero: for $$0<\epsilon< 1$$ the homeomorphism $$\phi_\epsilon :I\ni x \mapsto \max(\epsilon x, 2x-1)\in I$$ gives $$\|f\circ \phi_\epsilon-g\|_\infty<\epsilon$$. But of course for any homeomorphism $$\phi$$ from $$I$$ to itself we have $$f\circ\phi=\phi\neq g$$, as the former is injective and the latter is not. $$*$$ On the positive side, note that if for continuous $$f$$ and $$g$$ from $$I$$ to $$X$$ one has $$f(I)\neq g(I)$$, that is w.l.o.g. $$f(t_0)\notin g(I)$$ for some $$t_0\in I$$ , then for any homeomorphism $$\phi:I\to I$$, $$d_\infty(f,g\circ\phi)\ge \min_{t\in I} d_X(f(t_0), g(t))>0$$, so that the Fréchet distance $$\tilde d(f,g)$$ is non-zero.

Therefore, if $$f$$ and $$g$$ are injective and have zero Fréchet distance, then they are both homeomorphisms with the compact $$f(I)=g(I)$$ so $$\phi:=f^{-1}\circ g$$ is a homeomorphism $$I\to I$$ such that $$g=f\circ\phi$$. (rmk: At this point one also sees that $$\phi:I\to I$$ is increasing, because a decreasing homeomorphism would always give a positive Fréchet distance between $$f$$ and $$f\circ\phi$$, for any non-constant curve $$f$$).

(Nothing changes if we replace $$I$$ with a compact space $$K$$, where in the definition of the analogous Fréchet distance the quotient is over all homeomorphisms $$K\to K$$.)

• I would like to advertise my old question again: there the distance between curves is defined in a slightly different way, it identifies more than just homeomorphic reparametrizations, and so the maps from your example define the same curve in that sense, but there still can be different curves with the same images.
– erz
Jul 1, 2019 at 6:57
• Yes, in the other question non-decreasing continuous bijective reparametrizations are allowed for the equivalence (but I focused on this question only). Jul 1, 2019 at 7:53
• Thanks for the answer and comments. In your most recent comment Pietro I believe you mean "surjective" instead of "bijective"? I need to think about how this distinction plays out for general compact K, at the moment I don't see a natural generalization of "continuous non-decreasing surjection". Jul 1, 2019 at 14:47
• Yes sorry, indeed, I meant "surjective" Jul 1, 2019 at 16:56
• It seems that for general compact $K$ there isn't much to say for the "non-decreasing" version, but if $K$ is a compact metric space then perhaps an analogue of the continuous non-decreasing surjections is the closure of the set of homeomorphisms from $K$ to $K$ within the set of continuous maps from $K$ to $K$ in the uniform topology. Jul 1, 2019 at 19:42