Distance from a point to a line defined in R^N

[heymaniknowyou]

$\frac{}{}$Hello,

I've been trying to search for a general description for the Euclidean distance from a point to a line formula in $\mathbb{R}^n$. This line is assumed to be a straight line where a directional vector $f \in \mathbb{R}^n$ is constant and known, and a constant point on the line is known, $y \in \mathbb{R}^n$.

For the 2D and 3D cases this is quite simple. Given a point $X_0 = (x_0,y_0,z_0)$ the distance is $\frac{|f \times (y - X_0)|}{|f|}$ where the cross product is obvious for these cases.

I guess what I'm most unclear on is the cross product in higher dimensions and furthermore the euclidean distance in higher dimensions. I think a general understanding of one will eventually lead into the other.

Thanks for your help.

Best
S

 

[tiny-tim]

welcome to pf!

hello heymaniknowyou! welcome to pf!

hint: the general point on the line is y + ft,

and you want y + ft - x to be perpendicular to f ​

 

[Tinyboss]

Since you mentioned cross products and distance in higher dimensions, I'll expand a little on tiny-tim's answer. The norm $|v|$ of a vector $v$ in Euclidean space of any dimension is defined in terms of the dot product: $|v|^2=v\cdot v$. Then the distance between vectors is just the norm of their difference: $d(x,y)=|x-y|$.

Cross products are more interesting. For some pretty high-tech reasons, the cross product (i.e. an anti-commutative function that takes two vectors and gives back one vector orthogonal to the given ones) exists only in dimensions 3 and 7. Luckily, as tiny-tim explained, you only need the scalar (dot) product to solve this problem in any dimension.

 

[tiny-tim]

… the cross product (i.e. an anti-commutative function that takes two vectors and gives back one vector orthogonal to the given ones) exists only in dimensions 3 and 7.

how does it work in 7 ?

 

[Muphrid]

It's basically voodoo in 7 dimensions. What people need is the wedge product, not the cross product, and an understanding of dealing with bivectors and other such objects.

It is really, really easy to geometry on objects that don't go through the origin using projective geometry. Consider a 2d space, spanned by basis vectors $e_1, e_2$. Add one extra dimension with basis vector $e_0$. The plane that is 1 unit from the origin in the $e_0$ direction is taken to be the real 2d plane.

The convenience of this geometry is that lines in our real 2d plane that don't go through the origin can be thought of as the intersections of 2d subspaces with our real 2d plane. Given two points on our real 2d plane $p$ and $q$, the real line containing them is $L = p \wedge q$, and the shortest distance from that line to the origin is $e_0 \cdot (e_0 \wedge L)$.

There are a lot of symbols here that might not be understood, so let me give an example. Let $L$ be the line through x=1, y=0 and x=0, y=1. By simple geometry, we know that the distance from the origin to this line is $1/\sqrt{2}$. Let's verify that with projective geometry.

Let $p = e_0 + e_1$ and $q = e_0 + e_2$. The line $L$ is then $p \wedge q = e_0 \wedge e_2 + e_1 \wedge e_0 = e_{02} + e_{10} + e_{12}$. First, we find the volume that the 2d subspace makes with $e_0$. To do this, we just wedge in another $e_0$ on the front:

$$e_0 \wedge L = e_0 \wedge (e_{02} + e_{10} + e_{12} = e_{012}$$

And then we find the part of this volume that is perpendicular to $e_0$. This gives us the "footprint" or "shadow" of the 2d subspace on the real 2d plane. This quantity is called the "moment" $M$ of the line.

$$M = e_0 \cdot (e_0 \wedge L) = e_{12}$$

Now, we also need the direction of the line, which is found by $a = e_0 \cdot L = e_0 \cdot (e_{02} + e_{10} + e_{12})= e_2 - e_1 + 0$. We need this because the moment is made up of two parts: the direction $a$ and a support vector $d$--which is the vector to the closest point, which is what we're interested in. We just multiply the moment $M$ by $a$ on the right to help extract $d$. More specifically, we're going to multiply by $a^{-1} \equiv a/a^2$ on the right:

$$d = Ma^{-1} =e_{12} (e_2 - e_1)/2 = (e_1 + e_2)/2$$

The length of this vector is clearly $\sqrt{2}/2$, and we've found not only the distance but the vector to this point. You probably already know that vector if you have the equation of the line, but here we've found it just by starting with two points on the line.

We can extend this to arbitrary dimensions because the wedge product (and all of the generalized products used here) is valid in such spaces, where the cross product is not. So we just need the following:

$$\begin{align*}M &= e_0 \cdot (e_0 \wedge L) \\ a &= e_0 \cdot L \\ d &= Ma^{-1} \end{align*}$$

And that's it. This works in any number of dimensions. The projective geometry does introduce a little more overhead and may be a little harder to visualize, but it makes the process of finding the distance to a line (and indeed, to a plane or beyond) very mechanical.

This gives the distance from a line to the origin; translation should be enough to find the distance to an arbitrary point.

(You can also find the line $L$ with a point on the line and a direction also. Everything else follows from that.)

 

[heymaniknowyou]

hello heymaniknowyou! welcome to pf!

hint: the general point on the line is y + ft,

and you want y + ft - x to be perpendicular to f ​

Hmmm. Okay. I definitely got it. Thanks for your help. For some reason I was thinking that the cross product would be the only way to go and I forgot completely about the pretty little dot product. So I just found the projection of (y - x) on f and subtracted that from (y - x), so simple that I can't believe it went over my head. Ha!

Thanks for your help. I appreciate it, also thanks for welcoming me to the community. I've always been a lurker, and never asked any questions or answered any questions, but I think I'll start now. :)

Best
S

 

[tiny-tim]

… the pretty little dot product …

and so much more friendly than the cross product!

 

[heymaniknowyou]

and so much more friendly than the cross product!

I should have just started with that route for this idea. oh well.