Noncontracting Jordan curves

A simple closed curve {\Gamma} on the plane can be parameterized by a homeomorphism {f\colon \mathbb T\to \Gamma} in infinitely many ways. It is natural to look for “nice” parameterizations, like nonexpanding ones in the previous post. This time, let us look for noncontracting parameterizations: {|f(a)-f(b)|\ge |a-b|} for all {a, b\in \mathbb T}. Note that Euclidean distance is used here, not arclength. And we still want {f} to be a homeomorphism. Its noncontracting property simply means that the inverse {f^{-1}} is nonexpanding aka 1-Lipschitz.

What are some necessary conditions for the existence of a noncontracting parameterization? We can mimic the three from the earlier post Nonexpanding Jordan curves, with similar proofs:

  1. The curve must have length at least {2\pi}.
  2. The curve must have diameter at least 2.
  3. The curve must enclose some disk of radius 1. (Apply Kirszbraun’s theorem to {f^{-1}} and note that the resulting Lipschitz map G of the plane will attain 0 somewhere, by a topological degree / winding number argument. Any point where G = 0 works as the center of such a disk.)

This time, the 3rd item supersedes both 1 and 2. Yet, the condition it presents is not sufficient for the existence of a noncontracting parameterization. A counterexample is a disk with a “comb-over”:

combover

Indeed, suppose that {g=f^{-1}} is a nonexpanding map from this curve onto the unit circle. Let {1 = A < B < C} be the three points at which the curve meets the positive x-axis. Since every point of the curve is within small distance from its arc AB, it follows that {g(AB)} is a large subarc of {\mathbb T} that covers almost all of the circle. But the same argument applies to the arcs {g(BC)} and {g(CA)}, a contradiction.

No matter how large the enclosed disk is, a tight combover around it can force arbitrarily large values of the Lipschitz constant of {f^{-1}}. Sad!

What about sufficient conditions?

  1. It is sufficient for the curve to be star-shaped with respect to the origin, in addition to enclosing the unit disk. (Equivalent statement: {\Gamma} has a polar equation {r = r(\theta)} in which {r \ge 1}.) Indeed, the nearest-point projection onto a convex set is a nonexpanding map, and projecting {\Gamma} onto the unit circle in this way gives the desired parameterization.
  2. It is sufficient for the curve to have curvature bounded by 1. I am not going into this further, because second derivatives should not be needed to control a Lipschitz constant.

Recall that for nonexpanding parameterizations, the length of the curve was a single quantity that mostly answered the existence question (length at most 4 — yes; length greater than {2\pi} — no). I do not know of such a quantity for the noncontracting case.

Nonexpanding Jordan curves

A simple closed curve {\Gamma} on the plane can be parameterized by a homeomorphism {f\colon \mathbb T\to \Gamma} in infinitely many ways. It is natural to look for “nice” parameterizations: smooth ones, for example. I do not want to require smooth {\Gamma} here, so let us try to find {f} that is nonexpanding, that is {|f(a)-f(b)|\le |a-b|} for all {a, b\in \mathbb T}. Note that Euclidean distance is used here, not arclength.

What are some necessary conditions for the existence of a nonexpanding parameterization?

  1. The curve must have length at most {2\pi}, since nonexpanding maps do not increase length. But this is not sufficient: an equilateral triangle of sidelength {2\pi/3} has no nonexpanding parameterization, despite its length being {2\pi}.
  2. The curve must have diameter at most 2 (which the triangle in item 1 fails). Indeed, nonexpanding maps do not increase the diameter either. However, {\mathrm{diam}\,\Gamma\le 2} is not sufficient either: an equilateral triangle of sidelength {2} has no nonexpanding parameterization, despite its diameter being 2 (and length {6 < 2\pi}).
  3. The curve must be contained in some closed disk of radius 1. This is not as obvious as the previous two items. We need Kirszbraun’s theorem here: any nonexpanding map {f\colon \mathbb T\to \Gamma} extends to a nonexpanding map {F\colon \mathbb R^2\to\mathbb R^2}, and therefore {f(\mathbb T)} is contained in the closed disk of radius 1 centered at {F(0)}. (This property fails for the triangle in item 2.)

The combination of 1 and 3 (with 2 being superseded by 3) still is not sufficient. A counterexample is given by any polygon that has length {2\pi} but is small enough to fit in a unit disk, for example:

crown
Uneasy lies the head that cannot find a nonexpanding parameterization

Indeed, since the length is exactly {2\pi}, a nonexpanding parametrization must have constant speed 1. But mapping a circular arc onto a line segment with speed 1 increases pairwise Euclidean distances, since we are straightening out the arc.

Since I do not see a way to refine the necessary conditions further, let us turn to the sufficient ones.

  1. It is sufficient for {\Gamma} to be a convex curve contained in the unit disk. Indeed, the nearest-point projection onto a convex set is a nonexpanding map, and projecting the unit circle onto the curve in this way gives the desired parameterization.
  2. It is sufficient for the curve to have length at most 4. Indeed, in this case there exists a parameterization {f\colon \mathbb T\to\Gamma} with {|f'|\le 4/(2\pi) = 2/\pi}. For any {a, b\in \mathbb T} the length of the shorter subarc {\gamma} between {a} and {b} is at most {(\pi/2)|a-b|}. Therefore, the length of {f(\gamma)} is at most {|a-b|}, which implies {|f(a)-f(b)|\le |a-b|}.

Clearly, neither of two sufficient conditions is necessary for the existence of a nonexpanding parameterization. But one can consider “length {\le 2\pi} is necessary, length {\le 4} is sufficient” a reasonable resolution of the problem: up to some constant, the length of a curve can decide the existence one way or the other.

Stay tuned for a post on noncontracting parameterizations…

The least distorted curves and surfaces

Every subset {A\subset \mathbb R^n} inherits the metric from {\mathbb R^n}, namely {d(a,b)=|a-b|}. But we can also consider the intrinsic metric on {A}, defined as follows: {\rho_A(a,b)} is the infimum of the lengths of curves that connect {a} to {b} within {A}. Let’s assume there is always such a curve of finite length, and therefore {\rho_A} is always finite. All the properties of a metric hold, and we also have {|a-b|\le \rho_A(a,b)} for all {a,b\in A}.

If {A} happens to be convex, then {\rho_A(a,b)=|a-b|} because any two points are joined by a line segment. There are also some nonconvex sets for which {\rho_A} coincides with the Euclidean distance: for example, the punctured plane {\mathbb R^2\setminus \{(0,0)\}}. Although we can’t always get from {a} to {b} in a straight line, the required detour can be as short as we wish.

On the other hand, for the set {A=\{(x,y)\in \mathbb R^2 : y\le |x|\}} the intrinsic distance is sometimes strictly greater than Euclidean distance.

Nontrivial distortion
Oops, the equation was supposed to be y=|x|, without the square

For example, the shortest curve from {(-1,1)} to {(1,1)} has length {2\sqrt{2}}, while the Euclidean distance is {2}. This is the worst ratio for pairs of points in this set, although proving this claim would be a bit tedious. Following Gromov (Metric structures on Riemannian and non-Riemannian spaces), define the distortion of {A} as the supremum of the ratios {\rho_A(a,b)/|a-b|} over all pairs of distinct points {a,b\in A}. (Another term in use for this concept: optimal constant of quasiconvexity.) So, the distortion of the set {\{(x,y) : y\le |x|\}} is {\sqrt{2}}.

Gromov observed (along with posing the Knot Distortion Problem) that every simple closed curve in a Euclidean space (of any dimension) has distortion at least {\pi/2}. That is, the least distorted closed curve is the circle, for which the half-length/diameter ratio is exactly {\pi/2}.

Distortion of a closed curve
Distortion of a closed curve

Here is the proof. Parametrize the curve by arclength: {\gamma\colon [0,L]\rightarrow \mathbb R^n}. For {0\le t\le L/2} define {\Gamma(t)=\gamma(t )-\gamma(t+L/2) } and let {r=\min_t|\Gamma(t)|}. The curve {\Gamma} connects two antipodal points of magnitude at least {r}, and stays outside of the open ball of radius {r} centered at the origin. Therefore, its length is at least {\pi r} (projection onto a convex subset does not increase the length). On the other hand, {\Gamma} is a 2-Lipschitz map, which implies {\pi r\le 2(L/2)}. Thus, {r\le L/\pi}. Take any {t} that realizes the minimum of {|\Gamma|}. The points {a=\gamma(t)} and {b=\gamma(t+L/2)} satisfy {|a-b|\le L/\pi} and {\rho_A(a,b)=L/2}. Done.

Follow-up question: what are the least distorted closed surfaces (say, in {\mathbb R^3})? It’s natural to expect that a sphere, with distortion {\pi/2}, is the least distorted. But this is false. An exercise from Gromov’s book (which I won’t spoil): Find a closed convex surface in {\mathbb R^3} with distortion less than { \pi/2}. (Here, “convex” means the surface bounds a convex solid.)

Walking dogs and comparing sticks

Then he dropped two in at once, and leant over the bridge to see which of them would come out first; and one of them did; but as they were both the same size, he didn’t know if it was the one which he wanted to win, or the other one. — A. A. Milne

It’s useful to have a way of measuring how different two sticks (or fir cones) are in size, shape, and their position in a river. Yes, we have the Hausdorff distance {d_H} between sets, but it does not take into account the orientation of sticks. And it performs poorly when the sticks are broken: the Hausdorff distance between these blue and red curves does not capture the disparity of their shapes:

Small Hausdorff distance, totally different curves
Small Hausdorff distance, totally different curves

Indeed, {d_H} is relatively small here, because from any point of red curve one can easily jump to some point of the blue curve, and the other way around. However, this kind of measurement completely ignores the fact that curves are meant to be traveled along in a continuous, monotone way.

There is a concept of distance that is better suited for comparing curves: the Fréchet distance {d_F}. Wikipedia gives this (folklore) description:

Imagine a dog walking along one curve and the dog’s owner walking along the other curve, connected by a leash. Both walk continuously along their respective curve from the prescribed start point to the prescribed end point of the curve. Both may vary their speed, and even stop, at arbitrary positions and for arbitrarily long. However, neither can backtrack. The Fréchet distance between the two curves is the length of the shortest leash that is sufficient for traversing both curves in this manner.


To get started, let’s compute this distance for two oriented line segments {AB} and {CD}. The length of the leash must be at least {|AC|} in order to begin the walk, and at least {|BD|} to finish. So,

\displaystyle    d_F(AB,CD) \ge \max(|AC|, |BD|)

In fact, equality holds here. In order to bound {d_F} from above, we just need one parametrization of the segments. Take the parametrization proportional to length:

\displaystyle    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. (By the way, this proof works in every CAT(0) metric space.)


In general, the Fréchet distance is not realized by constant-speed parametrization. Consider these two curves, each with a long detour:

Symmetry breaking
Symmetry breaking

It would be impractical for the dog and the owner to go on the detour at the same time. One should go first while the other waits for his/her/its turn. In particular, we see symmetry breaking here: even for two perfectly symmetric curves, the Fréchet-optimal parametrizations would not be symmetric to each other.


It is not obvious from the definition of {d_F} whether it is a metric; as usual, it’s the triangle inequality that is suspect. However, {d_F} indeed satisfies the triangle inequality. To prove this, we should probably formalize the definition of {d_F}. Given two continuous maps {f,g} from {[0,1]} into {\mathbb R^2} (or any metric space), define

\displaystyle    d_F(f,g) = \inf_{\phi,\psi}\max_{[0,1]} |f\circ \phi-g\circ \psi|

where {\phi} and {\psi} range over all nondecreasing functions from {[0,1]} onto itself. Actually, we can require {\phi} and {\psi} to be strictly increasing (it only takes a small perturbation), which in dog/owner terms means they are not allowed to stop, but can mosey along as slowly as they want. Then we don’t need both {\phi} and {\psi}, since

\displaystyle    \max_{[0,1]} |f\circ \phi-g\circ \psi| = \max_{[0,1]} |f -g\circ (\psi\circ \phi^{-1})|

So, given {f,g,h} we can pick {\phi} such that {\max_{[0,1]} |f-g\circ \phi|} is within {\epsilon} of {d_F(f,g)}; then pick {\psi} such that {\max_{[0,1]} | g\circ \phi - h\circ \psi | } is within {\epsilon} of {d_F(g,h)}. Then

\displaystyle    d_F(f,h)\le \max_{[0,1]} |f- g\circ \phi|+\max_{[0,1]} |g\circ \phi - h\circ \psi|   \le d_F(f,g)+d_F(g,h)+2\epsilon

and the triangle inequality follows.