# What does the reparameterization mean in Fréchet distances?

I am trying to understand the definition of frechet distance but I am struggling to understand the reparameterization part in the definition. I got the following definition from wikipedia

Let A and B be two given curves in S. Then, the Fréchet distance between $$\mathbf A$$ and $$\mathbf B$$ is defined as the infimum over all reparameterizations $$\alpha$$ and $$\beta$$ of $$[0,1]$$ of the maximum over all $$t \in [0,1]$$ of the distance in $$\mathbf S$$ between $$\mathbf{A(\alpha(t))}$$ and $$\mathbf{B(\beta(t))}$$.

What does it mean by reparameterizations $$\alpha$$ and $$\beta$$ of $$[0,1]$$ of the maximum over all $$t \in [0,1]$$? Can anyone explain it with an example.

## 1 Answer

The wikipedia page (https://en.wikipedia.org/wiki/Fréchet_distance ) refers to a reparametrization as a continuous, non-decreasing surjection, so the Fréchet distance considers all possible curves $$\alpha$$ and $$\beta$$ that are non-decreasing surjections, finds the value of $$t$$ at which their difference is a maximum, and then takes the greatest of all those maxima.

A surjection from $$[0,1]$$ to $$[0,1]$$ is a map $$\alpha$$ such that there exists some $$x$$ in $$[0,1]$$ such that $$\alpha(x)=y$$ has a solution for all $$y\in[0,1]$$. It's possible for any $$x$$ to map to more than one $$y$$, the important thing is that no $$y$$ is missed out.

The simplest example of a reparametrization is the trivial one $$\alpha_1(x)=x$$. This is clearly surjective since $$\alpha_1(x)=y$$ has the solution $$x=y$$ for all $$y\in[0,1]$$. It is also non-decreasing since if $$x_1 then $$\alpha_1(x_1)<\alpha_1(x_2)$$ for all $$x_1,x_2\in[0,1]$$.

A more interesting reparametrization is $$\alpha_2(x) = \frac{\sin x}{\sin 1}$$ The function $$\sin$$ is monotonically increasing on $$[0,1]$$, as is its inverse $$\sin^{-1}$$ -- see the graphs. Dividing through by $$\sin 1$$ ensures that $$\alpha(0)=0$$ and $$\alpha(1)=1$$ so we achieve surjectivity on $$[0,1]$$ as required.

Suppose now you have two parabolic curves: $$A(t):= t^2$$ and $$B(t) = t^2+t/2+1/4$$. Reparametrizing with $$\alpha_1$$ doesn't change the curves at all, but when we reparametrize with $$\alpha_2$$ we get $$A(\alpha(t)) = \left( \frac{\sin t}{\sin 1} \right)^2 \quad \mbox{and}\quad B(\alpha(t)) = \left( \frac{\sin t}{\sin 1} \right)^2 + \frac{\sin t}{2 \sin 1} +1/4$$ Since the parabolae are strictly increasing, and the reparamatrization (being non-decreasing) doesn't change that, they have their maxima at $$t=1$$, and you can quickly calculate that $$|A(1)-B(1)| = \frac{3}{4} = |A(\alpha(1)) - B(\alpha(1))|$$