# What is the shortest distance between skew lines in N dimensions?

I have two skew lines in $\mathbb{R}^N$ ($N > 2$) defined as $\vec{x} = \vec{x}_A + \vec{d}_A t$ and $\vec{x} = \vec{x}_B + \vec{d}_B s$ ($t, s \in \mathbb{R}$). Now, I'd like to calculate the shortest distance between those lines. In 3D, this seems to be rather simple since the cross product $[\vec{d}_A \times \vec{d}_B]$ is a vector. However, in $\mathbb{R}^N$, there is an infinite number of vectors that are perpendicular to $\vec{d}_A$ and $\vec{d}_B$ and that lie on a subset $H^{\perp}$ of dimension $N - 2$.

My question is: How can one calculate the minimal distance without generalizing the cross product to $N$ dimensions?

You could compute the minimum of

$$d(s,t)=\Vert(\vec x_A+\vec d_At)-(\vec x_B+\vec d_Bs)\Vert=\Vert(\vec x_A-\vec x_B)+\vec d_At-\vec d_Bs\Vert$$

using basic analysis. In more detail: the above gives you a function $\mathbb R^2\rightarrow \mathbb R$. Compute its gradient, and look for zeros.

Hint: Even easier, use $d(s,t)^2$.

• Thanks for your answer! I though of minimizing $d(s, t)^2$ too. This would give me two points $P_A$ and $P_B$ that lie on either line, and the vector connecting the points $\vec{v}_{AB}$ would give the direction. However, I still have a problem with the uniqueness of $\vec{v}_{AB}$. It's true that $|\vec{v}_{AB}|$ is the minimal distant I am after, but how many vectors in $H^{\perp}$ would have the same distance?.. Is my logic correct? Feb 20, 2017 at 10:16
• I'm not sure what you mean with "vectors in $H^\bot$ having a distance". Only the vector $\vec v_{AB}$ gives you the shortest connection between the lines. Of course, there are other vectors perpendicular to $\vec d_A$ and $\vec d_B$ at the same time, but if they are not a solution to your minimization, they cannot point from one line to the other while being also short as $\vec v_{AB}$. Feb 20, 2017 at 10:28
• Yes, this was exactly what I meant. In this sense, $\vec{v}_{AB}$ must be unique since it's a) perpendicular to $\vec{d}_A$ and $\vec{d}_B$ and b) points from one line to the other. Other vectors from $H^{\perp}$ satisfy only a). Thanks for clarifying. Feb 20, 2017 at 10:38

It's worth noting that the 3-dimensional case is the most general case. If $$x(s) = p + s u$$ and $$y(t) = q + t v$$ generate the lines then the distance is the minimum norm of the residual $$r(s, t) = x(s) - y(t) = w + s u - t v$$ where $$w = p-q$$. The residual lies in the vector space spanned by $$u$$, $$v$$ and $$w$$. Within that space it occupies the 2-dimensional affine plane through $$w$$ with directions $$u$$ and $$v$$, assuming $$u$$ and $$v$$ are independent. We get the minimum norm residual by projecting parts of $$w$$ parallel to the $$uv$$ plane. If $$u$$ and $$v$$ are unit vectors, we get an orthogonal basis for the plane: $$\hat{u} = u, \hat{v} = (1 - u u^T) v$$. The distance is $$\|(1 - \hat{u} \hat{u}^T - \hat{v} \hat{v}^T /(\hat{v}^T \hat{v})) w\|$$.

Compared to cross product solution for the 3-dimensional case, you'll note that projecting onto the cross product of $$u$$ and $$v$$ is equivalent to the projection operator $$1 - \hat{u} \hat{u}^T - \hat{v} \hat{v}^T /(\hat{v}^T \hat{v})$$ when $$u$$ and $$v$$ are independent. More generally, if $$P$$ is an orthogonal projection onto a subspace then $$1-P$$ is the orthogonal projection onto the subspace's orthogonal complement.

What I went through is really just a special case of solving a least-squares problem with Gram-Schmidt. You can calculate the distance between arbitrary affine subspaces by a similar process. Let $$A, B$$ be linear maps into a vector space $$V$$ and let $$a, b$$ be points in $$V$$. Then $$a + \text{im}(A)$$ and $$b + \text{im}(B)$$ are affine subspaces of $$V$$. Their distance is the minimum norm of the residual $$r(x, y) = a-b + Ax - By$$. This is just a least-squares problem for a block matrix $$C$$ composed of $$A$$ and $$-B$$. Let $$z = [x, y]$$, $$c = a-b$$ and $$C = [A, -B]^T$$. Then $$c + Cz = a-b + Ax - By$$.