What does the reparameterization mean in Fréchet distances?
$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.
geometry frechet-derivative hausdorff-distance
edited Jan 13 at 12:35
postmortes
1,89321117
asked Jan 12 at 8:30
RafiRafi
1
$endgroup$
add a comment |
$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.
geometry frechet-derivative hausdorff-distance
edited Jan 13 at 12:35
postmortes
1,89321117
asked Jan 12 at 8:30
RafiRafi
1
$endgroup$
add a comment |
$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.
geometry frechet-derivative hausdorff-distance
edited Jan 13 at 12:35
postmortes
1,89321117
asked Jan 12 at 8:30
RafiRafi
1
$endgroup$
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.
geometry frechet-derivative hausdorff-distance
geometry frechet-derivative hausdorff-distance
edited Jan 13 at 12:35
postmortes
1,89321117
asked Jan 12 at 8:30
RafiRafi
1
edited Jan 13 at 12:35
postmortes
1,89321117
asked Jan 12 at 8:30
RafiRafi
1
edited Jan 13 at 12:35
postmortes
1,89321117
edited Jan 13 at 12:35
postmortes
1,89321117
edited Jan 13 at 12:35
postmortes
1,89321117
1,89321117
asked Jan 12 at 8:30
RafiRafi
1
asked Jan 12 at 8:30
RafiRafi
1
asked Jan 12 at 8:30
RafiRafi
1
1
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$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 $yin[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 $yin[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_2in[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))|$
answered Jan 13 at 12:40
postmortespostmortes
1,89321117
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3070703%2fwhat-does-the-reparameterization-mean-in-fr%25c3%25a9chet-distances%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 $yin[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 $yin[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_2in[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))|$
answered Jan 13 at 12:40
postmortespostmortes
1,89321117
$endgroup$
add a comment |
$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 $yin[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 $yin[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_2in[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))|$
answered Jan 13 at 12:40
postmortespostmortes
1,89321117
$endgroup$
add a comment |
$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 $yin[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 $yin[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_2in[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))|$
answered Jan 13 at 12:40
postmortespostmortes
1,89321117
$endgroup$
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 $yin[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 $yin[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_2in[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))|$
answered Jan 13 at 12:40
postmortespostmortes
1,89321117
answered Jan 13 at 12:40
postmortespostmortes
1,89321117
answered Jan 13 at 12:40
postmortespostmortes
1,89321117
answered Jan 13 at 12:40
postmortespostmortes
1,89321117
1,89321117
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3070703%2fwhat-does-the-reparameterization-mean-in-fr%25c3%25a9chet-distances%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
