# Intersection of lines in higher dimensions

Given two lines in the parametric form (where $p$ is a point on the line, $\hat{v}$ is a unit direction vector and $t$ is the parameter)

$q_0 = p_0 + t_0 \hat{v_0} \\ q_1 = p_1 + t_1 \hat{v_1}$

What is the general solution for detecting the intersection of lines in arbitrary dimensions?

The 3D formula I know is based on 2-ary cross product, which doesn't generalize to higher dimensions. In 2D you can use the perp dot product instead. What about dimensions 4 and higher?

The question is basically, if exists scalars $t_0$ and $t_1$ such that $$p_0 + t_0v_0 = p_1 + t_1 v_1.$$
So you just need to know if the vectors $p_1-p_0$, $v_0$, and $v_1$ are linearly independent, since the preceding sentence is the same as $$(p_0 - p_1) + t_0 v_0 - t_1 v_1 = 0.$$
So arrange $p_1-p_0$, $v_0$, and $v_1$ in a matrix and test to see if the matrix has full rank. If it does not, then you can use this fact to find a linear dependence among the columns, which will yield an intersection of the lines.
• On a computer, it is. The computational time complexity is $O(N^3)$. – plasmacel Jan 13 '17 at 21:06
• How big is your $N$? Do you need to do this a lot of times? – Zach Boyd Jan 13 '17 at 21:07