Distance between two lines II

Suppose we are given two lines, , defined as follows

where , and .  Let vector-valued functions and be defined as and , so that the two lines can be written in the form

.

Suppose that we want to compute the distance between these two lines. Back in December 2008, I wrote a very long post in which I derived from first principles an expression for the distance between two lines in . To cut a long story short, the distance between and is given by

.

My earlier post was quite conceptual and theoretical. In this post I focus on actually computing the distance between two given lines.

__________

Introduction

Note that the difference vector can be written in matrix form, as follows

.

Let . Then, the squared 2-norm of the difference vector can be written as

where are defined as follows

Note that , and also that is a Gramian matrix, which means that is either positive definite or positive semidefinite. Therefore, function is convex in , and we conclude that the minimum exists.

The pair that minimizes the 2-norm is the same one that minimizes the squared 2-norm and, hence, we have the unconstrained quadratic program

which can be solved analytically. The gradient of the objective function must vanish at the minimum

and, hence, we have a linear system of two equations in two unknowns

.

If , then the system of equations has a single unique solution. However, if , there are infinitely many solutions. Let us consider both cases separately.

__________

Non-parallel lines

If matrix is invertible, we obtain the unique minimizer . Thus, the minimum squared 2-norm of the distance vector is

Let . Then, and . Hence, we obtain

and, finally, the distance between lines and , , is the following

.

If direction vectors are linearly independent, i.e., the two given lines are non-parallel, then is invertible, and we have a unique minimizer. Intuitively, this makes sense.

__________

Non-parallel lines

Suppose now that the direction vectors are linearly dependent, , where . This corresponds to the case where the two lines are parallel (or coincident). In this case

which is clearly non-invertible. The linear system of equations, , now has a redundant equation. Eliminating this redundant equation, we obtain an underdetermined system

.

which has infinitely many solutions. We have one equation and two unknowns, i.e., one degree of freedom. Let us choose . Hence, we obtain

and

.

Let . Note that represents an orthogonal projection along vector . Hence, a distance-minimizing difference vector would be

.

Note that this difference vector is not unique (there are infinitely many alternatives). Finally, we obtain the distance between the two parallel lines

.

If is singular and , we conclude that the two lines are coincident.

__________

Implementation

Here’s a MATLAB script that computes the distance between two lines:

function d = dist(x0,y0,u,v)

 % extract dimension
 n = size(x0,1);

 % build P, Q matrices
 P = [u -v];
 Q = P' * P;

 % build projection matrix
 Pi_u = (u * u') / (u' * u);

 % compute distance
 if det(Q) == 0
 d = norm((eye(n,n) - Pi_u)*(x0-y0),2);
 else
 d = sqrt((x0-y0)'*(eye(n,n) - P*inv(Q)*P')*(x0-y0));
 end

__________

Related:

• Distance between two lines

L’importance d’être seul

A humbling passage from Grothendieck‘s Récoltes et Semailles:

J’ai eu l’occasion, dans ce monde des mathématiciens qui m’accueillait, de rencontrer bien des gens, aussi bien des aînés que des jeunes gens plus ou moins de mon âge, qui visiblement étaient beaucoup plus brillants, beaucoup plus “doués” que moi. Je les admirais pour la facilité avec laquelle ils apprenaient, comme en se jouant, des notions nouvelles, et jonglaient avec comme s’ils les connaissaient depuis leur berceau – alors que je me sentais lourd et pataud, me frayant un chemin péniblement, comme une taupe, à travers une montagne informe de choses qu’il était important (m’assurait-on) que j’apprenne, et dont je me sentais incapable de saisir les tenants et les aboutissants. En fait, je n’avais rien de l’étudiant brillant, passant haut la main les concours prestigieux, assimilant en un tournemain des programmes prohibitifs.

La plupart de mes camarades plus brillants sont d’ailleurs devenus des mathématiciens compétents et réputés. Pourtant, avec le recul de trente ou trente-cinq ans, je vois qu’ils n’ont pas laissé sur la mathématique de notre temps une empreinte vraiment profonde. Ils ont fait des choses, des belles choses parfois, dans un contexte déjà tout fait, auquel ils n’auraient pas songé à toucher. Ils sont restés prisonniers sans le savoir de ces cercles invisibles et impérieux, qui délimitent un Univers dans un milieu et à une époque donnée. Pour les franchir, il aurait fallu qu’ils retrouvent en eux cette capacité qui était leur à leur naissance, tout comme elle était mienne: la capacité d’être seul.

__________

Here’s one possible translation of Grothendieck’s passage:

I’ve had the chance, in the world of mathematics that bid me welcome, to meet quite a number of people, both among my “elders” and among young people in my general age group, who were much more brilliant, much more “gifted” than I was. I admired the facility with which they picked up, as if at play, new ideas, juggling them as if familiar with them from the cradle — while for myself I felt clumsy, even oafish, wandering painfully up an arduous track, like a dumb ox faced with an amorphous mountain of things that I had to learn (so I was assured), things I felt incapable of understanding the essentials or following through to the end. Indeed, there was little about me that identified the kind of bright student who wins at prestigious competitions or assimilates, almost by sleight of hand, the most forbidding subjects.

In fact, most of these comrades who I gauged to be more brilliant than I have gone on to become distinguished mathematicians. Still, from the perspective of 30 or 35 years, I can state that their imprint upon the mathematics of our time has not been very profound. They’ve all done things, often beautiful things, in a context that was already set out before them, which they had no inclination to disturb. Without being aware of it, they’ve remained prisoners of those invisible and despotic circles which delimit the universe of a certain milieu in a given era. To have broken these bounds they would have had to rediscover in themselves that capability which was their birth-right, as it was mine: the capability to be alone.