Line-line Intersection - N-line Intersection

N-line Intersection

In two dimensions, more than two lines almost certainly do not intersect at a single point. Similarly, in three or more dimensions, even two lines almost certainly do not intersect. However, in two or more dimensions, we can usually find a point that is mutually closest to two or more lines in a least-squares sense.

In the two-dimensional case, first, represent line i as a point on the line and a normal vector, perpendicular to that line. That is, if and are points on line 1, then let and let

which is the unit vector along the line, rotated by 90 degrees.

Note that the distance from a point, x to the line (p, n) is given by

.

And so the squared distance from a point, x, to a line is

.

the sum of squared distances to many lines is the cost function:

This can be rearranged:

To find the minimum, we differentiate with respect to x and set the result equal to the zero vector:

so

and so

.

This can be generalized to any number of dimensions by noting that is simply the (symmetric) matrix with all eigenvalues unity except for a zero eigenvalue in the direction along the line providing a seminorm on the distance between and another point giving the distance to the line. In any number of dimensions, if is a unit vector along the ith line, then

becomes

where I is the identity matrix, and so

.