2
$\begingroup$

Given are two $m$-dimensional affine subspaces embedded in $\mathbb{R}^n$

$$a_{1i}x_{1i} + a_{2i}x_{2i} + \cdots + a_{ni}x_{ni} = a_{0i}$$

$$b_{1i}x_{1i} + b_{2i}x_{2i} + \cdots + b_{ni}x_{ni} = b_{0i}$$

where $i = 1 ... m$ define the $m$ hyperplanes defining each of the subspaces. The goal is to compute their intersection. If they do not intersect, also compute the (orthogonal) shortest distance between the two subspaces.

Not sure if I formulated the problem correctly, so I'll provide examples:

  • The intersection of two lines in 3D (respectively defined by the intersection of two planes, i.e., $m=2$) can either be empty or a point. In case they do not intersect, I would like to compute the shortest distance between the lines.
  • The intersection of two planes in 4D (respectively defined by the intersection of 3 hyperplanes, i.e., $m=3$) can either be empty, a point, or a line. In case they do not intersect, I would like to compute the shortest distance between the two planes.

My approach would be to put all the hyperplanes in a matrix and compute the nullspace of the matrix to compute the span of the solution. However, I would like to get this confirmed by somebody else and I am not sure how to compute the distance. The final goal is to implement this in a program, so any (pseudo) code would be highly appreciated.

$\endgroup$
5
  • $\begingroup$ In 3D those are 2 planes (not lines) $\endgroup$
    – G Cab
    Jun 10, 2019 at 0:20
  • $\begingroup$ @GCab I had a mistake in my definition of the problem. Please checkout the updated description. $\endgroup$ Jun 10, 2019 at 0:28
  • 1
    $\begingroup$ For the intersection, you can just throw both sets of equations into a single system, just as you thought. This question and answer shows one method of computing the distance. Note that the latter includes the former—if the spaces intersect, the $\lambda$’s and $\mu$’s will be zero. $\endgroup$
    – amd
    Jun 10, 2019 at 8:11
  • $\begingroup$ @amd That's what I was looking for. Excellent. Thanks. $\endgroup$ Jun 10, 2019 at 18:36
  • $\begingroup$ Another way to go is to project the difference between a pair of representative points of the two spaces onto the intersection of their orthogonal complements. The other computation is more direct, and probably more efficient. I’ll write that up in more detail when I get a chance. $\endgroup$
    – amd
    Jun 10, 2019 at 18:39

2 Answers 2

2
$\begingroup$

You could certainly toss all of the hyperplane equations into a single system and solve them (computing the null space of a matrix as you suggest is one way), but if the intersection is empty you’ll have to do something else do compute the distance between the spaces. This answer gives you a way to do both with a single computation that uses the information you have directly. When the intersection is non-empty, the $\lambda$’s and $\mu$’s will be zero and you can extract the intersection from the $A$ and $B$ parts of the solution vector.

As mentioned in the linked answer, the minimum distance between the spaces is measured along a line that’s orthogonal to them both. This suggests an alternative method for computing the distance between two affine spaces that’s a generalization of a way to compute the distance between two lines in $\mathbb R^3$: choose a representative point for each space and project their difference orthogonally onto the intersection of the orthogonal complements of the spaces. Here the orthogonal complement of the first space is spanned by the $\mathbf a_i$ and similarly the orthogonal complement of the second is spanned by the $\mathbf b_i$, but you’ll have to find a solution to each system of equations to get the two representative points. There are well-known methods for computing the intersection of the spans of two sets of vectors and orthogonal projection onto a span is also well-known. I expect that the method in the linked answer will be more efficient for larger-dimensional subspaces, though, since this will only tell you that the spaces intersect, but not produce their intersection without more work.

Taking the example from the linked answer, we have the two lines in $\mathbb R^3$ given by $$x+y+z=1\\2x-y+3z=2$$ and $$x-2y-z=-1\\3x-4y+z=1.$$ The intersection of the null spaces is spanned by $(7,-5,11)^T$ and we can find $(1,0,0)^T$ and $(3,2,0)^T$ for our representative points. The distance between the two lines is therefore $${\left((3,2,0)-(1,0,0)\right)\cdot(7,-5,11)\over\sqrt{7^2+5^2+11^2}} = \frac4{\sqrt{195}}.$$

$\endgroup$
1
$\begingroup$

Let's start with 3D and 2 lines. If they are parallel, normalizing their coefficients (the normal to both) , and dividing by the same factor the known term to the right, then the difference of the normalized known terms (taken in case with the absolute value) is the distance between the lines.

Can you then proceed and extend ?

$\endgroup$
1
  • $\begingroup$ Thanks, I could find parallel (hyper-)planes that contain the lines and then compute the orthogonal distance as $d = \vert a_0 - b_0 \vert / \Vert \mathbf{a} \Vert = \vert a_0 - b_0 \vert / \Vert \mathbf{b} \Vert$. How would I extend this to $m$ and $n$ dimensions? $\endgroup$ Jun 10, 2019 at 1:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .