0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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<x_2$ 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.

Graphs of sin and arcsin

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))|$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.