Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Represent the position of a unit-length, oriented segment $s$ in the plane by the location $a$ of its basepoint and an orientation $\theta$: $s = (a,\theta)$. So $s$ can be viewed as a point in $\mathbb{R^2} \times \mathbb{S^1}$. Now I'll define a metric on this space. Define the distance $d(s_1,s_2)$ between two positions of unit-length segments as the average distance between their corresponding points:
      Segments
Above the distances are about 0.31, 0.61, and 0.53, left-to-right.

So if the endpoints of $s_i$ are $a_i$ and $b_i$, then $d(s_1,s_2)$ is the average of the Euclidean distances between $(1-t) a_1 + t b_1$ and $(1-t) a_2 + t b_2$ as $t$ varies in $[0,1]$. This is indeed a metric, I believe, because the triangle inequality holds between corresponding points in three positions of the segment. This metric is intended to capture the intuitive notion of how much work is required to move $s_1$ to $s_2$.

My question is: What are the geodesics in this space under this metric? Certainly a pure translation of $s$ is a geodesic. It seems that a pure rotation by at most $\pi$ of $s$ about a point $p \in s$ should also be a geodesic, but even this is not so clear to me. Certainly a rotation about a point not on $s$ is (generally) not a geodesic. Of course the main interest would be in geodesics that mix translation and rotation, showing (locally) optimal repositioning paths.

I investigated this long ago when working on motion-planning algorithms ("moving a ladder"), but got quite blocked on this natural question. This superficially seems related to the Kakeya needle problem, but the metric I propose does not measure swept area. Perhaps it has been studied in some guise previously. If so, a pointer would be appreciated. Thanks!

Addenda. (26Sep11.) I just ran across this book, by V. A. Dubovit͡s︡kiĭ, which seems relevant: The Ulam problem of optimal motion of line segments, Translation Series in Mathematics and Engineering, Optimization Software, 1985. It may take some time for me to locate a copy...

(11Nov11). I finally have this book in my hands. The Preface by Hestenes says,

Dubovitskij has succeeded in solving in closed form a generalization of a problem of S[.] Ulam..: Among all continuous motions of an oriented line segment $S$ in $\mathbb{E}^n$ from one position to another, which preserves its length [...], find one for which the sum of the lengths of the paths swept by its endpoints is minimal.

The concentration here on the motion of the endpoints—in contrast to the average distance metric I proposed—seems to render these results as not directly relevant, although nevertheless quite interesting.

share|improve this question
    
Is this metric space a path metric space? i.e. are all computed distances actually realized by geodesic paths? –  j.c. Sep 22 '11 at 22:34
    
@jc: Good question! Until you asked it, I was unfamiliar with path metric spaces. Now investigating... –  Joseph O'Rourke Sep 22 '11 at 22:38
    
This is a bit of a side issue though - you can still have geodesics in a space even if the induced intrinsic distance doesn't agree with the original distance function. en.wikipedia.org/wiki/Intrinsic_metric –  j.c. Sep 22 '11 at 22:46
2  
Let $s_0$ and $s_1$ be your $s_1$ and $s_2$, respectively (and I'll use the same relabeling for $a_i$,$b_i$). For $\alpha\in[0,1]$, let $s_\alpha$ be the segment defined by $(1-\alpha)[(1-t)a_0+tb_0]+\alpha[(1-t)a_1+tb_1]$ for $t\in[0,1]$. If $s_\alpha$ is a unit segment for all $\alpha$, the distance between $s_0$ and $s_1$ can be realized as a path. If $s_\alpha$ is not always a unit segment (generically, its length will change as $\alpha$ varies), I think a geodesic between $s_0$ and $s_1$ will not realize the distance you defined... –  j.c. Sep 22 '11 at 23:04
    
as you are no longer able to take some "shortcut" through segments not of unit length? –  j.c. Sep 22 '11 at 23:04
add comment

4 Answers 4

Let us start with metric on $\mathbb R^4=\mathbb R^2\times \mathbb R^2$. Defined by norm $\|{*}\|$ defined by $$\|(x,y)\|=\int_0^1|t\cdot x+(1-t)\cdot y|\,dt,$$ where $|{ * }|$ denotes Euclidean norm on $\mathbb R^2$. This norm, is not strongly convex, so you should expect many geodesics between close points.

Now, your metric is the intrisic metric induced by on the hypersurface $\Sigma$ described by $|x-y|=1$. So, you have a Finsler metric on $\Sigma=\mathbb S^1\times \mathbb R^2$. The unit ball in the tangent plane is isometric the intersection of the ball in the above norm with 3-dimensional subspace in one special direction. It seems that this intersection is strongly convex. The metric is smooth (sinse there is a transitive isometric group action on $\mathbb S^1\times \mathbb R^2$). It reamins to write differential equasion for geodesic; this should be in any book on Finsler geometry. (It should be pain, but it might help.)

share|improve this answer
1  
@jc: sorry, now it is corrected. –  Anton Petrunin Sep 23 '11 at 2:31
    
@Anton: This is a great insight, to see the segment metric as an induced metric in $\mathbb{R}^4$! Hopefully it will help identify the geodesics. –  Joseph O'Rourke Sep 23 '11 at 11:05
add comment

In addition to Anton Petrunin's answer, here is a trick to simplify (and in some sense solve) the geodesic equation.

Since the metric has three-dimensional group of isometries (generated by rigid motions of the plane), the corresponding Noether's integrals make the geodesic flow completely integrable. More precisely, the first derivative is uniquely determined by the position and the values of the integrals. Actually a two-dimensional group is sufficient because for the third integral one can always take the speed (= the norm of the velocity vector) of a geodesic.

So let's use invariance under parallel translations only. We have a manifold of all unit segments in the plane, and a tangent vector to that manifold can be thought of as the vector field along a segment (representing velocities of all its points). This vector field has a form $$ v(t) = tx + (1-t)y, \qquad t\in[0,1] $$ where $x,y\in\mathbb R^2$ are such that the vector $x-y$ is orthogonal to the segment. The norm of this tangent vector is $\int |v(t)| dt$ (as in Anton's answer), and the Noether integral corresponding to translations (if my quick computation is correct) boils down to the following: if $v$ is a velocity vector of a geodesic represented in the above form, then $$ \int_0^1 \frac{v(t)}{|v(t)|} \ dt = V_0 $$ where $V_0$ is a constant (for each geodesic) vector in the plane. This vector $V_0$ (and, say, the assumption that the geodesic is unit-speed) determines the parameters $x$ and $y$ in the formula for $v(t)$ uniquely (as a function of the segment's current direction), so the geodesic equation is reduced to a 1st order ODE. Furthermore, the above integral can be found as an explicit (but weird) function of $x$ and $y$, so the equation becomes easy to solve, at least numerically.

By the way, I second Jean-Marc Schlenker's proposal to consider quadratic mean of the distances (i.e. $L^2$ norm rather than $L^1$), especially if you have any physics-related application in mind. In this case the metric is Riemannian, the energy is just the standard kinetic energy of the moving segment, so the Noether intergrals are just the standard conservation laws: the linear momentum and the angular momentum. And the geodesics are very simple: the segment rotates at a fixed angular speed while its midpoint (the barycenter) moves along a straight line with a constant speed.

share|improve this answer
    
@Sergei: That's great that "the geodesic equation is reduced to a 1st order ODE" through your analysis! Thanks so much for your attention! I take J.-M. S.'s and your point re quadratic mean, but--alas!-- Work = Force $\times$ distance, not $\times$ distance $^2$. :-) But I will mull over the considerable advantages of the $L_2$ norm... –  Joseph O'Rourke Sep 24 '11 at 14:10
add comment

What follows are just some illustrations, not a full answer; please refer to Anton Petrunin's answer for a nice description of the 4 dimensional geometry that the original question is embedded in.

Here's a bit of Mathematica code to generate some crude discrete approximations to geodesics. Given the two endpoint segments $s_0,s_1$, I create $n$ segments on the naïve $s_\alpha$ path I defined in the comments above, normalize their lengths to one, and then vary the positions of the endpoints of these intermediate segments with Mathematica's FindMinimum function to find an approximate geodesic. The code I wrote looks for a local minimum of an objective function with two terms: one is just the sum of the distances between all the intermediate segments and the other is a constraint that forces the distances between each pair of adjacent segments on the path to be equal (otherwise the intermediate segments all flow to the endpoints). The segments are all constrained to have unit length.

As Mathematica is not really good at a serious minimization problem, the code runs rather slowly (finding a discrete path with $n=10$ takes about 7 minutes), but perhaps you might still be able to get some more direct intuition for the geodesics by playing around with it in different cases. It's a start, anyways.

Below is an image of one example. The endpoints are a segment with endpoints $(0,0)$ to $(1,0)$ (orange) and $(1,0)$ to $(1,1)$ (red), and I approximated a geodesic with a chain of $n=10$ segments. The path begins with the orange segment sliding upwards a tiny bit to "yellow", and then the segments rotates counter clockwise and translate right until they reach red.

The segment distance between red and orange is $\frac{1}{8}\left(4+\sqrt{2}\log(3+2\sqrt{2})\right)\approx0.8116$, but the length of the approximate geodesic is $0.865$. Each pair of "adjacent" segments in the picture has a segment distance roughly 0.096 between them.

With $n=10$, the length has not converged to high accuracy! For $n=7,8,9$ the lengths of my approximations are $0.857,0.884,0.876$, respectively. In any case, it's clear that the length of the true geodesic will be greater than the distance between the endpoints. You might stare at this picture and imagine the true geodesic "hugging" the 3 dimensional unit length segment hypersurface in the 4D space, whereas the distance measures a "chord" through the 4 dimensional space of segments with arbitrary length.

10 point approximation to geodesic

update

As Joseph O'Rourke points out in the comments, the code is not very good with (anti-)parallel configurations. What seems to work is to give either segment a slight perturbation.

As an example, here's an approximate geodesic ($n=10$ points) between a segment with endpoints $(1,0)$ to $(2,0)$ (orange) and a segment with endpoints $(-1,0)$ to $(-1+\cos(\pi+0.001),\sin(\pi+0.001))\approx(-2+5\times10^{-7},0.001)$. The distance between the endpoints is $\approx3-2\times10^{-7}$, but the length of the depicted approximate geodesic is 3.30 (with steps of about 0.367).

Interestingly, this approximate geodesic seems to break symmetry in two ways. First, the segments rotate clockwise while traveling left. Second, the picture doesn't have left-right symmetry, which means that the first half of the journey is different from the second half (an analogue of this can be seen in the example above too, which doesn't have reflection symmetry across the -45º line). Is the second effect just due to discretization or non-convergence of the minimization? I don't know how to show that the true geodesics must be symmetric if there's some symmetry relating the two endpoints.

10 point approximation to geodesic between antiparallel segments

code snippet for this:

a1 = {1, 0}; b1 = {2, 0}; a2 = {-1, 0}; b2 = {-1 + Cos[\[Pi] + .001], Sin[\[Pi] + .001]};
Timing[anti3 = FindChain[{a1, b1}, {a2, b2}, 10]]
SegmentDist2[{a1, b1}, {a2, b2}]
Table[SegmentDist2[anti3[[i]], anti3[[i + 1]]], {i, 9}]
Sum[SegmentDist2[anti3[[i]], anti3[[i + 1]]], {i, 9}]
Graphics[Table[{Hue[i/Length[anti3]], Line[anti3[[i]]]}, {i, Length[anti3]}]]
share|improve this answer
    
@jc: Thanks for this effort! I tried to run your code for antiparallel, collinear placements, e.g., from $(1,0)\rightarrow(2,0)$ to $(−1,0)\rightarrow(−2,0)$, but I must not understand the functions. I think this is an interesting special case. –  Joseph O'Rourke Sep 23 '11 at 11:53
    
@Joseph O'Rourke: for (anti-)parallel configurations, the minimum finder ends up dividing by zero - the simplest fix is to try perturbing one of the segments slightly away from this case. For the parallel case, the issue seems to be a removable singularity in the analytical formula SegmentDist2, I guess this might be removed by using the numerical integration function SegmetnDist instead. –  j.c. Sep 23 '11 at 14:18
    
For the anti-parallel case, the problem is a little tougher; in my naïve initial "guess" for the geodesic path, the linear interpolant $s_\alpha$ might degenerate to a single point, and also the reflection symmetry might have to be broken? If you insist on using exactly anti-parallel configurations, this might be fixed by a smarter or a perturbed choice of initial guess (the variable "test" in FindChain)? One might also have to go to the numerical integrator too, I'm not sure. Perhaps the analytical formula I'm using can be improved to take care of these cases, too. –  j.c. Sep 23 '11 at 14:23
    
Fascinating, jc! I like the subproblem you isolated: Prove or disprove that geodesics must reflect symmetry present in the initial and final segment placements. –  Joseph O'Rourke Sep 23 '11 at 14:56
    
I've updated my notebook with the snippet (and I also replaced the "Line" graphics with the more helpful "Arrow"). –  j.c. Sep 23 '11 at 18:04
add comment

A useful keyword for this problem is the Wasserstein distance, see wikipedia. I believe that this Wasserstein distance, for $p=1$, provides a variant of the distance you're considering but for unoriented segments. There is a well-developed theory here, in particular concerning the geodesics and their behavior. Incidentally things my turn out to be easier if you take the means of the squares of the distances, rather than of the distances.

share|improve this answer
    
Thanks, J.-M.! I would never have looked at this, although I have heard of its alias, the earth mover's distance. Great connection! –  Joseph O'Rourke Sep 23 '11 at 16:04
    
I just found that the book, Gradient flows: in metric spaces and in the space of probability measures, contains a chapter entitled, "The Wasserstein distance and its behavior along geodesics." This may help. –  Joseph O'Rourke Sep 23 '11 at 16:12
    
Thanks Joseph. Actually I'm not sure it's that useful, because the Wasserstein metric geodesics will not respect the structure of the segments -- you'll have segments at the beginning and at the end, but not in between. In other terms the space of segments is a kind of submanifold in the space of measures, but it's not geodesic. Back to your original question, it's probably necessary to do a computation to obtain the ODE describing geodesics, as mentioned by Sergei. –  Jean-Marc Schlenker Sep 24 '11 at 14:07
add comment

Your Answer

 
discard

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.