Find 3D line incident on four given 3D lines

How can I find the straight line incident on 4 given straight lines, all embedded in 3D space?

I'm usually comfortable with linear algebra; my understanding of projective geometry is limited.

(My ultimate goal is to find a probability distribution for the straight line incident on N given straight lines, where N-1 of them are uncertain/fuzzy. This may be an entirely different question; this question is just to get me started.)

(I will be offline for about 20 hours.)

The other post got too long and the LaTeX starts to lag.

One can also reason geometrically, directly in $\mathbb{R}^3$ and $\mathbb{RP}^3$. I am going to assume that $\mathbb{RP}^3$ = $\mathbb{R}^3 \, \cup P_{\infty}$ where $P_{\infty}$ is the plane at infinity. Let $l_1, \, l_2, \, l_3$ and $l_4$ be the four lines such that no two intersect (or are parallel). Take three of them, say $l_1, \, l_2, \, l_3$. Then there is a unique quadratic surface $H$ (aka quadric) in $\mathbb{R}^3$ (and in fact in $\mathbb{RP}^3$) such that all three lines $l_1, \, l_2, \, l_3$ lie on that quadric $H$. In fact, $H$ is a doubly ruled surfaces, i.e. there is one family of non intersecting lines (call them $l_{\alpha} \, : \, \alpha$) and another family of non intersecting lines (call them $m_{\beta} \, : \, \beta$). Any line $l_{\alpha}$ from the first family intersects any line $m_{\beta}$ from the second family. The three lines $l_1, \, l_2, \, l_3$ are members of the first family $l_{\alpha}$ (they determine it). Think of $H$ as a one sheeted hyperboloid (up to projective transformation) or a hyperbolic paraboloid if you wish (wiki these and you will see what I am talking about).

Now, if you know the three lines in coordinates, you will be able to write explicitly the quadratic equation for $H$.

Assume you have a line $m$ that intersects all three lines $l_1, \, l_2, \, l_3$. Since $m$ intersects $l_1$ and $l_2$, where $l_1 \cap l_2 = \varnothing$, then $m$ intersects $H$ at two different points. Recall that a line and a qadratic surface can intersect at no more than two points, unless the line lies completely on the surface. However, $m$ intersects also line $l_3$ which is disjoint from the other two lines, so $m$ has a third point of intersection with $H$ so $m$ must lie on $H$. Consequently, $m$ must belong to one of the two families of lines on $H$ and since all lines from $l_{\alpha}$ are disjoint, $m$ is a member of the other family $m_{\beta}$.

Finally, one concludes that if there is a line $m$ that intersects all four lines $l_1, \, l_2, \, l_3$ and $l_4$ it must be a line lying on $H$ so the forth line $l_4$ must have a common point with $H$. The converse is also true, if $l_4$ intersects $H$ at a point $P$, then one can take the unique line $m$ from family $m_{\beta}$ that passes through point $P$. Then $m$ also would intersect the other three lines $l_1, \, l_2, \, l_3$.

Thus, the solution to your problem boils down to construct the equation of the quadric $H$, generated by the three lines $l_1, \, l_2, \, l_3$, and to check how many intersection points has $l_4$ with $H$.

1. If there are two (which is max if all lines are in general position, i.e. if $l_4$ is not a member of $l_{\alpha}$, in which case there would be infinitely many solutions), then there are two lines $m_1$ and $m_2$ that intersect all four lines $l_1, \, l_2, \, l_3$ and $l_4$.

2. If $l_4$ is tangent to $H$, then there is exactly one line $m$ that intersects all four lines $l_1, \, l_2, \, l_3$ and $l_4$.

3. If $l_4$ doesn't intersect $H$ at all, then there is no solution.

• I'm so lucky you came across my question! Thanks again. – Museful Apr 13 '17 at 0:22
• @Museful No, thank you! It has been interesting to think about this problem. – Futurologist Apr 13 '17 at 1:34

I am assuming you would consider $\mathbb{RP}^3$ and not just $\mathbb{R}^3$ to make things more homogeneous. And I believe, assuming your four lines are in general position (i.e. meaning no two lines intersect in $\mathbb{RP}^3$). Then, generically, it seems like there might be a pair of lines that intersect four lines lines in the projective three-space in general position. However, there also might be one or no solution to this problem.

There are various approaches, some directly geometric, some a bit more sophisticated involving spaces of lines (the Plucker quadric, which is a type of Grassman manifold). I think in your case, it is more instructive to learn a bit about the Plucker quadric. One can do this using the conceptual construction of wedge product and exterior algebra. Consider $\mathbb{R}^4$ and as usual $\mathbb{RP}^3 = \big\{[u] \, : \, u \in \mathbb{R}^4 \big\}$ with $[u] = \big\{\lambda \, u \, \, : \,\, \lambda \in \mathbb{R}\setminus\{0\} \, \big\}$. Projective lines in the projective three space $\mathbb{RP}^3$ correspond to the projectivisation of two-dimensional vector subspaces in $\mathbb{R}^4$. If I fix a two-dimensional subspace in $\mathbb{R}^4$ I can define it as the span of two linearly independent vectors $u,v \in \mathbb{R}^4$ lying on it and I can form the wedge product $q = u \wedge v \, \in \, \wedge^{2} \,\mathbb{R}^4 = \mathbb{R}^4 \wedge \mathbb{R}^4$. Moreover, if $u_1, v_1$ are two different vectors spanning the same subspace as $u, v$, then there is $\lambda \in \mathbb{R}$ such that $u_1\wedge v_1 = \lambda (u \wedge v)$. This prompts us to projectivize the wedge product: $$\mathbb{P}(\wedge^{2} \,\mathbb{R}^4 ) = \big\{ [\omega] \,\, : \,\, \omega \in \wedge^2 \, \mathbb{R}^4\big\}$$ $$[\omega] = \big\{\lambda \, \omega \in \wedge^{2} \,\mathbb{R}^4 \,\, : \,\, \lambda \in \mathbb{R}\setminus\{0\}\big\}$$ and the elements that describe the lines in $\mathbb{RP}^3$, which is the same as the two dimensional subspaces of $\mathbb{R}^4$, have the form $[u \wedge v]$. However, not all elements of $\mathbb{P}(\wedge^{2} \,\mathbb{R}^4 )$ are of this form. How to distinguish the ones that define lines from the one that do not, i.e. when is an element of $\wedge^{2} \,\mathbb{R}^4$ of the form $u \wedge v$? As it turns out, $\omega \in \wedge^{2} \,\mathbb{R}^4$ has the form $\omega = u \wedge v$ if and only if $\omega \wedge \omega = 0$, where $\omega \wedge \omega \in \wedge^{4} \,\mathbb{R}^4$. Since there exists an isomorphism (non-canonical) $\phi : \wedge^{4} \,\mathbb{R}^4 \to \mathbb{R}$, we can define the complex bilinear dot product (nondegenerate bilinear form) $(\omega \cdot \sigma) = \phi(\omega \wedge \sigma)$ for $\omega, \sigma \in \wedge^2 \, \mathbb{R}^4$. Then, this dot product has two very important properties:

1. $(\omega \cdot \omega) = \phi(\omega \wedge \omega) = 0$ if and only if $\omega \wedge \omega = 0$ if and only if $\omega=u \wedge v$;

2. If two lines in $\mathbb{RP}^3$ intersect at a common point, then their corresponding two two-dimensional subspaces of $\mathbb{R}^4$ intersect at a common one dimensional subspace, spanned by a vector $v_0$, so the two lines will be represented by two wedge products $q_1 = u_1 \wedge v_0$ and $q_2 = u_2 \wedge v_0$ and so $(q_1 \cdot q_2) = \phi(q_1 \wedge q_2) = \phi(0) = 0$. The converse is also true, if two wedge products $q_1 = u_1 \wedge v_1$ and $q_2 = u_2 \wedge v_2$ are such that $(q_1 \cdot q_2) = \phi(q_1 \wedge q_2) = \phi(0) = 0$, then there is at least one vector $v_0 \in \mathbb{R}^4$ such that $q_1 = \lambda_1 (w_1 \wedge v_0)$ and $q_2 = \lambda _2 (w_2 \wedge v_0)$.

With this information at hand, define the quadric $$\hat{Q} = \big\{\omega \in \wedge^2 \, \mathbb{R}^4 \,\, : \,\, (\omega \cdot \omega) = 0 \big\}.$$ Then its projectivization $$Q =\big\{\, [\omega] \in \mathbb{P}(\wedge^2 \, \mathbb{R}^4) \,\, : \,\, \omega \in \hat{Q} \, \big\} = \big\{\, [\omega] \in \mathbb{P}(\wedge^2 \, \mathbb{R}^4) \,\, : \,\, (\omega \cdot \omega) = 0 \, \big\}.$$ Thus $\mathbb{G}(1,3) \cong Q$. If you have a plane $H$ in $\mathbb{RP}^3$ and a point on it $p \in H$ one can pick two different lines $l_1$ and $l_2$ lying on $H$ and passing through $p$. Then $H$ is spanned by these two lines. Let $l_1 = [u_1 \wedge v_0]$ and $l_2 = [u_2 \wedge v_0]$, where $p = [v_0]$. Denote $\hat{l}_1 = u_1 \wedge v_0$ and $\hat{l}_2 = u_2 \wedge v_0$. Then any other line on $H$ passing through $p$ should look like $$l = [\lambda_1 \hat{l}_1 + \lambda_2 \hat{l}_2] = [\lambda_1 u_1 \wedge v_0 + \lambda_2 u_2 \wedge v_0] = [(\lambda_1 u_1 + \lambda_2 u_2) \wedge v_0]$$ for any $\lambda_1, \lambda_2 \in \mathbb{R}$. Thus the set $\Sigma_{p,H}$ of all lines lying on $H$ and passing through $p$ is the projectivisation of a two-dimensional subspace of $\wedge^2 \, \mathbb{R}^4$ so it is a one-dimensional line on $\mathbb{P}(\wedge^2 \, \mathbb{R}^4)$ composed of elements $l = [\lambda_1 \hat{l}_1 + \lambda_2 \hat{l}_2] \in \Sigma_{p,H}$ with the property that $$\big((\lambda_1 \hat{l}_1 + \lambda_2 \hat{l}_2)\cdot (\lambda_1 \hat{l}_1 + \lambda_2 \hat{l}_2) \big) = 0$$ which means that $l \in Q \cong \mathbb{G}(1,3)$ and hence $\Sigma_{p,H} \subset Q \cong \mathbb{G}(1,3)$. Observe that $\dim_{\mathbb{R}} \big(\wedge^2 \, \mathbb{R}^4\big) = 6$, so $\wedge^2 \, \mathbb{R}^4 \cong \mathbb{R}^6$ and so $\mathbb{P}(\wedge^2 \, \mathbb{R}^4) \cong \mathbb{RP}^5$ and thus $Q = \mathbb{G}(1,3)$ is a four dimensional projective quadric in $\mathbb{RP}^5$. The signature of the quadratic form $(\sigma \cdot \omega)$ is $+,+,+,-,-,-$ so technically, $Q = \mathbb{G}(1,3)$ lies in the projectivizaiton of $\mathbb{R}^{3,3}$.

The converse. Let $\Sigma$ be a line lying on the conic $Q$. Then there are two different points $[l_1]$ and $[l_2]$ lying on $\Sigma$, where $l_i = u_i\wedge v_i$ for $i=1,2$. So these two points span $\Sigma$, i.e. $[l] \in \Sigma$ if and only if $[l] = [\lambda \, l_1 + \lambda_2 \, l_2] \, \in \, \Sigma \, \subset \, Q$ for any complex numbers $\lambda_1, \lambda_2 \in \mathbb{R}$ not simultaneously zero. Then since $[l] \in \Sigma$ and $\Sigma \subset Q$, $$0 = (l \cdot l) = \big((\lambda \, l_1 + \lambda_2 \, l_2) \cdot(\lambda \, l_1 + \lambda_2 \, l_2)\big) = \lambda_1^2 (l_1 \cdot l_1) + 2\lambda_1 \lambda_2 (l_1 \cdot l_2) + \lambda_2^2 (l_2 \cdot l_2) = 2\lambda_1 \lambda_2 (l_1 \cdot l_2)$$ because $(l_1\cdot l_1) = (l_2 \cdot l_2) = 0$ as $[l_1], [l_2]$ are points lying on the quadric $Q$. Hence $(l_1 \cdot l_2) = 0$. But this means that $\phi(l_1 \wedge l_2)=0$ i.e. $u_1 \wedge v_1 \wedge u_2 \wedge v_2 = 0 \in \wedge^4 \, \mathbb{R}^4$. The latter statement means that the four vectors $u_1, v_1, u_2, v_2 \in \mathbb{R}^4$ cannot span the whole space and are linearly dependent. Hence there is a vector $v_0 \in \mathbb{R}^4$ such that $$\text{span}\{u_1, v_1\} \cap \text{span}\{u_2, v_2\} = \text{span}\{v_0\}$$ Hence $l_1 = [u_1 \wedge v_0]$ and $l_2 = [u_2 \wedge v_0]$ and $[\lambda_1 \, l_1 + \lambda_2\, l_2] = [\,(\lambda_1 v_1 + \lambda_2 u_2) \wedge v_0]$ represents the two-space $\text{span}\{\lambda_1 v_1 + \lambda_2 u_2, v_0\}$ in $\mathbb{R}^4$ which means that all the lines from $\Sigma$ pass through the same point $p = [v_0] \in \mathbb{RP}^3$ all of them are contained in the plane $$H = \mathbb{P}\big(\text{span}\{u_1, u_2, v_0\}\big) \, \subset \, \mathbb{RP}^3$$

Now, after this introduction to the construction and the structure of the Plucker quadric, let us identify $\wedge^2 \, \mathbb{R}^4$ together with the bilinear form $\phi(\omega \wedge \sigma)$ with $\mathbb{R}^6$ with a bilinear form $(\omega \cdot \sigma)$ of signature $+,+,+,-,-,-$. This is possible as discussed above. Now, if we pick four lines $l_1, \, l_2, l_3$ and $l_4$ from $\mathbb{RP}^3$ in general position (no two intersect), then this is equivalent to selecting the corresponding four points $l_1, \, l_2, l_3$ and $l_4$ on the four dimensional projective quadric $Q \, \subset \, \mathbb{RP}^5$. These four points $l_1, \, l_2, l_3$ and $l_4$ span a three dimensional projective subspace $L$ of $\mathbb{RP}^5$ so that $L \cap Q$ is, in general, a two dimensional projective surface (a two dimensional quadric) lying inside $Q$. Then the polar space $L^*$ of $L$ with respect to the quadric $Q$ is a one dimensional projective line $L^*$ which could intersects the four dimensional quadric $Q$ at two points lying on $Q$. The intersection is nonempty (generlic) depending on the general position of the original four lines, which determines the signature of the spaces $L$ and $L^*$. Based on this signature, one can determine how many solutions the problem could have. The claim is that any of the points $l \in L^* \cap Q$ is a line in $\mathbb{RP}^3$ that intersects the four lines $l_1, l_2, l_3$ and $l_4$.

To understand this from another point of view, look at the pre-projective space $\mathbb{R}^6$. Then the four lines $l_1, \, l_2, l_3$ and $l_4$ of $\mathbb{RP}^3$ give rise to four one dimensional vector subspaces $\hat{l}_1, \, \hat{l}_2, \hat{l}_3$ and $\hat{l}_4$ of $\mathbb{R}^6$. The span $\hat{L}$ of $\hat{l}_1, \, \hat{l}_2, \hat{l}_3$ and $\hat{l}_4$ is a four dimensional vector subspace of $\mathbb{R}^6$. Then it's orthogonal complement $\hat{L}^*$ in $\mathbb{R}^6$ with respect to the bilinear form $(\omega \cdot \sigma)$ is the two dimensional vector subspace $$\hat{L}^* = \{ \, \sigma \in \mathbb{R}^6 \,\, | \,\, (\sigma \cdot \omega) = 0 \, \text{ for all } \omega \in \hat{L} \, \}$$ After projectivization, this construction of orthogonality becomes polarity with respect to $Q$. Recall that the five dimensional cone $$\hat{Q} = \{ \, \omega \in \mathbb{R}^6 \,\, | \,\, (\omega \cdot \omega) = 0 \, \}$$ is what becomes the four dimensional quadric $Q$ after projectivization. Moreover, $l \in Q \cap L^*$ is equivalent to $\hat{l} \in \hat{Q} \cap \hat{L}^*$ so for that reason $(\hat{l} \cdot \hat{l}_j) = 0$ for all $j=1,2,3,4$. Here I have abused notation, thinking of $\hat{l}$ and $\hat{l}_j$ as nonzero vectors, spanning the actual one dimensional subspaces $\hat{l}$ and $\hat{l}_j$ of $\mathbb{R}^6$. By construction, two lines $l$ and $l_j$ from $\mathbb{RP}^3$ intersect if and only if their representatives $l$ and $l_j$ from the Plucker quadric $Q$ satisfy $(\hat{l} \cdot \hat{l}_j) = 0$.

In your case, later you could consider introducing a probability measure on $Q$, which will allow you to write down probabilities of line incidences.

• Wow. Thank you for the time you spent on this! The problem is harder than I thought. I might have to spend some weeks learning what I have to learn to digest this. – Museful Apr 12 '17 at 21:38
• @Museful Wait, hold on, I was meaning to write also something about a more direct approach. However, I haven't had the time to do it. When I find time I can sketch some stuff in a separate answer, because the LaTeX of this one starts to lag, and then you can look at it and see if you would need more details. Nice question by the way, I like it. – Futurologist Apr 12 '17 at 22:07

I don't think the problem is well defined. If all 4 given lines go through a point O, any other line going through that point is incident on all 4. Similarly, if the 4 lines are co-planar, I can find an infinite number of lines incident on all 4. Now if you have for example 4 parallel lines incident on a plane, and the intersections form a non degenerate quadrilateral, there is no single line that intersects all of them