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

Question

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?

Answer 1

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$.

Answer 2

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$.