Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for a metric $d$ for smooth 2D curves. Hence $d(x,y)$ is the distance between the curves x and y. For the moment, we may assume that $x$ and $y$ are just directed line segments. Do you think the sum of distances between the corresponding points would work (for the said restricted kind of curves). And in general, how to do it?

Thus, does the definition $d(AB,CD) = d'(A,C)+d'(B,D)$ works for directed line segments $AB$, $CD$ (where $d'$ is a metric of points in the plane)?

Is there any example? Where can I find out more details?

share|cite|improve this question
If you're willing to have all your curves be parametrized over $[0,1]$. Then you can use $d(f,g)=\int_0^1 d(f(t), g(t))\, dt$. – Avi Steiner Feb 25 '13 at 22:15
Also, your metric for directed lines segments does in fact work. – Avi Steiner Feb 25 '13 at 22:20
Thanks for the reply (and the positive confirmation)! Can you also give some links for me to explore? – Pui Feb 25 '13 at 22:27
what's your mathematical background? – Avi Steiner Feb 25 '13 at 22:30
I took a course in differential geometry ~30 years ago. I need a metric for plane curves for my programming project. – Pui Feb 25 '13 at 22:35

1 Answer 1

A popular way of measuring distance between oriented curves is the Fréchet distance. As the Wikipedia puts it, $d_F(\gamma_1,\gamma_2)$ is the shortest length of a leash that allows a dog and its owner to walk along $\gamma_1$ and $\gamma_2$ in the specified direction (without backtracking).

For oriented line segments $AB$ and $CD$, this distance is equal to $ \max(|AC|, |BD|)$ where $|\cdot |$ is the pointwise distance. I reproduce the proof from my blog:

The length of the leash must be at least $ {|AC|}$ in order to begin the walk, and at least ${|BD|}$ to finish. So, $$ d_F(AB,CD) \ge \max(|AC|, |BD|) $$ In order to bound ${d_F}$ from above, we just need one parametrization of the segments. Take the parametrization proportional to length: $$ P=(1-t)A+tB,\quad Q=(1-t)C+tD $$ Then ${|PQ|^2}$ is the quadratic polynomial of ${t}$. Without doing any computations, we can say the coefficient of ${t^2}$ is nonnegative, because ${|PQ|^2}$ cannot be negative for any ${t\in\mathbb R}$. Hence, this polynomial is a convex function of ${t}$, which implies that its maximum on the interval ${[0,1]}$ is attained at an endpoints. And the endpoints we already considered.

This doesn't mean you should drop what you've been doing and replace sum by maximum. Since the maximum of two nonnegative numbers is within a factor of $2$ of their sum, the distance you are using is comparable to the Fréchet distance.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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