# Computing geodesics (or shortest paths)

I'm interested in computing geodesic curves (or locally shortest paths) on surfaces in 3D. We can assume that the surface is given in parametric form $(u,v) \mapsto \mathbf{S}(u,v)$. If it helps, we can even assume that the parameterization is given by polynomials of fairly low degree (say 3, 4, or 5). Further, we are given two points $\mathbf{P}_0 = \mathbf{S}(u_0,v_0)$ and $\mathbf{P}_1 = \mathbf{S}(u_1,v_1)$ lying on the surface.

Two questions:

(1) I want to compute a curve of minimal length between $\mathbf{P}_0$ and $\mathbf{P}_1$, and lying in the surface.

(2) I want to compute a curve between $\mathbf{P}_0$ and $\mathbf{P}_1$, lying in the surface, on which the geodesic curvature is zero at every point.

I believe questions (1) and (2) have a close relationship, though I'm not exactly sure what it is. The relationship is not particularly important to me; I mentioned it only because it might allow us to solve both problems with one method.

The surfaces I'm dealing with are "real world" ones -- think about the roof of a car, for example, or the upper surface of the wing of an aircraft. The surfaces are very smooth, and are usually convex, if that helps. There are important applications in manufacturing, which I can explain if anyone is interested.

Edit: After some more searching, I found this paper, which seems to have what I need. The ideas are quite similar to those in the accepted answer below.

• Have you studied calculus of variations? If not, you will find the method that you seek there. Sep 3, 2016 at 11:14
• @Lovsovs -- no, I have not, specifically, though I'm somewhat comfortable with optimisation problems in function spaces in general. Can you recommend any numerical methods for COV problems ?? Sep 3, 2016 at 11:17
• No, unfortunately I can't, but I'm sure they are out there. Sep 3, 2016 at 11:21
• It is not clear what your question is: are you interested in the relationship between (1) and (2), or in techniques for the computations at (1) and (2)? Sep 3, 2016 at 11:36
• You can always build a grid, calculating an orientation tensor of the manifold, assume a vector field with prescribed source and sink at start/end point and use the tensor field punishing any attempt to move in the "wrong" direction. (Assuming you are able to find such a punishing term that works for you). Sep 3, 2016 at 11:38

## 2 Answers

Ok, let me see if I get it right. You are interested in a computational method that finds the geodesic connecting two points. More precisely, you are looking for a reasonable discretization method, you are not necessarily looking for the differential-geometric explanation.

There is several different but equivalent (i.e. leading to the same result) characterizations of geodesics on a two dimensional surface embedded (immersed) in three space. So what I'm gonna say is by no means exhaustive of the subject.

In what follows I will use $u = (u_1,u_2)$ instead of $(u,v)$ and a point in three space will be $x = (x_1,x_2,x_3)$. So you have your surface $S : (u_1,u_2) \mapsto (x_1,x_2,x_3)$. We mostly work in $(u_1,u_2)$ coordinates and then, when we have some solution, we map it in 3D via $S$.

First, compute the metric tensor $g_{ij}(u)$ which is a 2 by 2 matrix of function $G(u) = \big( g_{ij}(u)\big)$ with components: $$g_{ij}(u) = \left(\frac{\partial S}{\partial u_i} \cdot \frac{\partial S}{\partial u_j}\right)$$ where $( \, \cdot \, )$ is the dot product in three space. On a surface in three space, as well as on any smooth manifold, the length of a smooth curve $u : [a,b] \to \mathbb{R}^2$ (curve given with respect to $u = (u_1,u_2)$ coordinates and parametrized as $u=u(t)$) with tangent vector (first derivatives with respect to parameter $t$) $\dot{u} = (\dot{u}_1, \dot{u}_2)^T$ is

$$\mathcal{L}[u] = \int_{a}^{b} \sqrt{\dot{u}(t)^TG\big( u(t)\big)\dot{u}(t)} \,\, dt = \int_{a}^{b} \sqrt{\dot{u}^TG\big( u\big)\dot{u}} \,\, dt$$

The distance between the points $u(a)$ and $u(b)$ is the minimum of $L[u]$ over all smooth curves connecting $u(a)$ to $u(b)$. Geodesics are curves that (locally) minimize $\mathcal{L}[u]$. Now, alongside the length functional, define the (kinetic) energy functional

$$E[u] =\frac{1}{2} \int_{a}^{b} \dot{u}(t)^TG\big( u(t)\big)\dot{u}(t) \,\, dt = \frac{1}{2}\int_{a}^{b} \dot{u}^TG\big( u\big)\dot{u} \,\, dt$$

Due to the Cauchy-Schwarz inequality, $(\mathcal{L}[u])^2 \leq 2(b-a) E[u]$ for any curve $u(t)$ with equality if and only if $\dot{u}^TG\big( u\big)\dot{u} \equiv const$ which happens when both functionals are optimized, which means that $\mathcal{L}[u]$ is optimized exactly when $E[u]$ is optimized and both are optimized by the same curve (geodesic). Bottom line, the optimizers of $E[u]$ are the geodesics so we can simply replace $\mathcal{L}[u]$ by $E[u]$.

If one denotes by $L(u,\dot{u}) =\frac{1}{2} \dot{u}^TG\big( u\big)\dot{u}$, aka the Lagriangian or the Lagrange function, then the energy functional becomes $$E[u] = \frac{1}{2} \int_{a}^{b} \dot{u}^TG\big( u\big)\dot{u} \,\, dt = \int_{a}^{b} L(u, \dot{u}) \, dt = \int_{a}^{b} L\Big(u(t), \dot{u}(t)\Big) \, dt .$$

Then, according to the calculus of variations, the optimizing curves of the functional $E$ ( which are the geodesics ) are the solutions of the Euler-Lagrange equations $$\frac{d}{dt}\Big(\, \frac{\partial L}{\partial \dot{u}}(u,\dot{u}) \, \Big) = \frac{\partial L}{\partial u}(u,\dot{u}).$$ After rearranging the terms of the latter equations, one gets the equations

\begin{align} &\ddot{u}_1 + \sum_{ij} \Gamma^1_{ij}(u) \, \dot{u}_i\dot{u}_j =0\\ &\ddot{u}_2 + \sum_{ij} \Gamma^2_{ij}(u) \, \dot{u}_i\dot{u}_j =0 \end{align}

which are exactly the geodesic equation written in terms of the Christoffel symbols $\Gamma^k_{ij}(u)$ of the Levi-Civita connection of the Riemannian metric $G(u)$. Geometrically, they express the fact, written in $(u_1,u_2)$-coordinates, that the curvature vector of the curve $S\big(u(t)\big)$ in three space has zero projection on the tangent plane to the surface $S$ at every point of the curve $S\big(u(t)\big)$ (i.e. the normal vector of the geodesic is aligned with the normal vector of the surface). The latter projection, of the normal vector of a curve onto the tangent plane, is in fact the geodesic curvature vector, so these equations say the geodesic curvature is zero.

Now, let's go back to the functional $E[u]$ because I suggest a straight-forward discretization of the method I outlined above as follows: replace the derivative $\dot{u}$ by a difference $(u^1 - u)/\varepsilon$ (or something even better if you wish) and consider the discrete Lagrangian $$L_{\varepsilon}(u,u^1) := L\left(\, u, \, \frac{u^1-u}{\varepsilon} \, \right) = \frac{1}{2\varepsilon^2} (u^1 - u)^T G\big( u\big)(u^1 - u).$$ By analogy with the continuous case, where the action is $E[u] = \int_{a}^{b} L(u,\dot{u})dt$, in the discrete case the energy is $$E_{\varepsilon}[u] = \sum_{k=0}^{N} L_{\varepsilon}\big(u^k,u^{k+1} \big)$$ where $u^0$ is your initial point and $u^{N+1}$ is your final point. Then, the critical discrete geodesic should simply be the solution to the algebraic equations $\nabla E_{\varepsilon}[u] = 0$ which componentwise leads basically to the discrete version of the Euler-Lagrange equations $$\frac{\partial L_{\varepsilon}}{\partial u^k}\big(u^{k-1}, u^k\big) + \frac{\partial L_{\varepsilon}}{\partial u^k} \big(u^{k}, u^{k+1}\big) = 0 \,\,\, \text{ for } \,\,\, k=1,...,N$$ $$u^0 = \text{ initial point, } \,\, u^{N+1} = \text{ finial point. }$$ The latter is a system of algebraic equations, something like $2 N$ equations and variables. The solution is a sequence of points $\,\, u^0, \, u^1, \, u^2, \, ... \, , \, u^{N+1} \,$ which should approximate the geodesic between $u^0$ and $u^{N+1}$. When you map them onto the surface in 3D via the map $S$ you get a sequence of points $\,\, S\big(u^0\big), \, S\big(u^1\big), \, S\big(u^2\big), \, ... \, , \, S\big(u^{N+1}\big) \,$
which lie on your surface and should be a good approximation to the smooth geodesic. You can interpolate between consecutive points (either the $u$'s or the $S(u)$'s) if you wish to get an actual curve.

Now, you have two parameters you need to adjust. These are $\varepsilon$ and $N$. Maybe a link between them makes sense, something like $\varepsilon = \frac{1}{N}$ or something even more sophisticated. I haven't thought about it too much. The smaller $\varepsilon$ and the larger the $N$, the better the approximation (hopefully :) ).

Now, to find discrete geodesics with a stating point and a direction vector, one can look locally at the discrete Euler-Lagrange equations and write them down using a simplified superscript notation $$\frac{\partial L_{\varepsilon}}{\partial u}\big(u^{(-1)}, u\big) + \frac{\partial L_{\varepsilon}}{\partial u}\big(u, u^{1}\big) = 0$$ Introduce the variable $p = \frac{\partial L_{\varepsilon}}{\partial u}\big(u, u^{1}\big)$. Then the discrete Euler-Lagrange equations become $$\frac{\partial L_{\varepsilon}}{\partial u}\big(u^{(-1)}, u\big) +p= 0$$ which shifted by one subscript turn into $\frac{\partial L_{\varepsilon}}{\partial u^1}\big(u, u^1\big) + p^1= 0$. Thus we obtain the equations $$p = \frac{\partial L_{\varepsilon}}{\partial u}\big(u, u^{1}\big)$$ $$p^1 = -\frac{\partial L_{\varepsilon}}{\partial u^1}\big(u, u^1\big).$$ If one can express $u^1$ as a function of $(u,p)$ from the first equation, then the second equation also gives us $p^1$ as a function of $(u,p)$. Thus we have obtained a map $\Phi : (u,p) \mapsto (u^1,p^1)$. Observe that this is a map $\Phi : T^*\mathbb{R}^2 \to T^*\mathbb{R}^2$, which turns out to be symplectic, because the Lagrangian $L_{\varepsilon}$ is in fact a generating function of the symplectomorphism $\Phi$. Then, given an initial point $u^0$ and a direction vector $v_0$, take let's say $u^1 =u_0 + \varepsilon \, v^0$ and obtain $p^0$. Then starting with $u = u^0$ and $p=p^0$, start iterating the map $\Phi$ getting $\big(u^{k+1}, p^{k+1}\big) = \Phi\big(u^{k}, p^{k}\big)$ obtaining again a sequence $\,\, u^0, \, u^1, \, u^2, \, ... \, , \, u^{k}, \,\, .... \,$ which approximates your geodesic (here you have another sequence $\,\, p^0, \, p^1, \, p^2, \, ... \, , \, p^{k}, \,\, .... \,$ which is a sequence somehow related to the dual vectors to the tangent vectors to your geodesic, but maybe that's not important for you).

Comment: As explained above, the discrete Euler-Lagrange equations are $\nabla E[u] = \nabla E( u^1, u^2, ..., u^k, ... u^n) = 0$, i.e. the multi-point $( u^1, u^2, ..., u^k, ... u^n)$ for which the gradient of $E( u^1, u^2, ..., u^k, ... u^n)$ is zero. Therefore, in the case of given initial and final point for the geodesic, a first line computational approach could be a gradient descent method (or a version of Newton's method). In the case of an initial point and a direction vector, simply iterate the map $\Phi$. Even if the map is not explicit, the problem is still slightly simpler because one goes step by step, every time solving only the system involving the variables $u, u^1, p, p^1$.

Comment: To make the gradient descent method a bit more efficient, one can choose a smart initial guess for the discrete geodesic $u^0,\, u^1, \, ..., \, u^{N+1}$. We have $u^0$ and $u^{N+1}$ fixed. These are the initial point and the end point. Denote by $\bar{u}(m) = \big(u^0, \, u^1(m),\, u^2(m), \, ...,\, u^{N}(m), \, u^{N+1} \big)$ a sequence of $N+2$ points at iteration $m$. Then say we use some sort of gradient descent $$\bar{u}(m+1) = \bar{u}(m) + \alpha_m \, \nabla E \big[\bar{u}(m)\big]$$ with starting point $\bar{u}(0) = \big(u^0, \, u^1(0),\, u^2(0), \, ...,\, u^{N}(0), \, u^{N+1}\big)$. If $\bar{u}(0)$ is picked carefully, then the gradient descent could make less iterations before arriving at a very good approximate solution to the problem $\nabla \, E[u] = 0$.

Suggestion 1: For instance (especially if your metric is not too curved or your points are not too far apart) take simply the segment between $u^0$ and $u^{N+1}$ and choose $N$ equally spaced points in between as a starting point $\bar{u}(0)$.

Suggestion 2: If you have some extra information, you can smartly use $u^0$ as a starting point and a second point $u^1$, then run the initial value iteration to create a discrete geodesic you can use as an initial guess for your gradient descent algorithm (or Newton's method or whatever numerical scheme you use to solve the discrete variation problem). That's why I have also discussed the initial value problem because one can use it as an auxiliary tool.

For instance, take $S(u^0)$ and $S(u^{N+1})$, the images of $u^0$ and $u^{N+1}$ on the surface $S$ in $\mathbb{R}^3$, and form the vector $\overrightarrow{u^{0}u^{N+1}}$, then project it onto the tangent plane at to the surface $S$ at the point $S(u^0)$. Write it as $$\text{proj}\Big( \overrightarrow{u^{0}u^{N+1}} \Big) = v_1 \, \frac{\partial S}{\partial u_1}(u^0) + v_2 \, \frac{\partial S}{\partial u_2}(u^0).$$ Form the vector $v=(v_1, v_2)^T$ (a tangent vector with respect to $(u_1, u_2)$-coordinates), rescale it to become small enough, and then use it as an intial value problem to generate a discrete geodesic that comes close to $u^{N+1}$. You can even get to a reasonable choice for $N$. Then use this geodesic as a starting point for your gradient descent method in order to get a much more accurate approximation of the geodesic connecting $u^0$ to $u^{N+1}$.

• Thanks very much. It will take me a while to absorb all this, but it looks very helpful. I'd like to upvote, but my voting buttons seem to have disappeared. Sep 5, 2016 at 0:47
• @bubba I hope it helps you solve whatever problem (practical or not) you are trying to solve. I added a comment regarding gradient descent method. It may give you some further ideas on how to get a possible approximate solutions. Sep 5, 2016 at 2:00
• I think there's a typo in your definition of $G$. The subscripts should be $i$ and $j$, right? The initial-value problem seems easier, but unfortunately that's not the one I'm faced with. Thanks again. Was finally able to give you an upvote. Sep 5, 2016 at 12:49
• @bubba Ah yes, I fixed it. Thank you. I just mentioned the initial value problem because it may come in handy. But I mainly discuss the boundary value problem: starting point - end point. To make your gradient descent method a bit more efficient, you can choose a good initial guess for the discrete geodesic $u^0, u^1,...$. Then the gradient descent will make less iterations before arriving at a very good solution. For instance (especially if your metric is not too curved) take simply the segment between $u^0$ and $u^{N+1}$ and choose $N+1$ equally spaced points in between as a start. Sep 5, 2016 at 14:48
• @bubba Or if you have some extra information, you can smartly use $u^0$ as a starting point and a second point $u^1$, then run the initial value iteration to create a discrete geodesic you can use as an initial guess for your gradient descent algorithm (or Newton's method or whatever numerical scheme you use to solve the discrete variation problem). That's why I discussed also the initial value problem because you can use it as an auxiliary tool. Sep 5, 2016 at 14:53

HINTS:

Both are parts of the same problem. Read topic of zero geodesic curvature in differential geometry. An ODE has to be solved. There is a unique geodesic of minimum length. Experimenting with cone geodesics is convenient for theory and visualization.

To practically trace such on an airplane wing for example use a wide 3M cello tape and start sticking along an approximate direction without frills on edges. Nudge/change its start orientation, come back until there is a hit at the other point by trial and error. Like shooting a point on an hill opposite with a gun along a curved trajectory where elevation angle is adjustable.

Numerical BVP shoot-through techniques are done in a similar way.

• I'd guess that you don't have much manufacturing experience. An iterative trial-and error process with cello-tape (Scotch tape, for Americans) would not be acceptable. That's the reason for the question. Sep 5, 2016 at 12:29
• Interestingly, your cello-tape experiment is quite close to the real application. Objects made from composites are often fabricated by laying down strips of carbon-fiber tape. Sep 5, 2016 at 12:51
• .. known as tape laying, never mind experience. An assumption of surfaces of revolution is a good start. A thick 3M American Scotchtape serves the purpose.The direction at start should be iterated in a Newton type iteration in a Boundary Value Problem. Sep 5, 2016 at 20:30