1
$\begingroup$

Given 3 homogeneous 2D points, $p=[p_x,p_y,1]$, $q=[q_x,q_y,1]$, and $v=[v_x,v_y,v_z]$, with $p$ and $q$ finite (last coordinate is $1$), but $v_z$ maybe either $1$ - finite or $0$ - at infinity:

Find two new 2D points $p'$, $q'$ s.t. $d(p,p')+d(q,q')$ is minimized, with $d(p,q)$ the Euclidian distance) and $ = 0$.

In words, find the line $l=[l_1,l_2,l_3]$ passing through $v$, that minimizes the sum of the Euclidean distances of $p$ and $q$ from $l$.

How can I find $l$? Even if only for the finite case where $v_z=1$.

1 Answers 1

1

At least for the infinite case ($v_z=0$), the solution will in general not be unique: any line passing between $p$ and $q$ will give the same distance. This is because as you move the line by an Euclidean distance of $a$ orthogonal to its direction, one distance will decrease by $a$ while the other will increase by that same amount, keeping the sum constant. This is why such approximation tasks usually minimize not the sum of errors but the sum of squared errors, often (but not necessarily) measured not orthogonal to the line but in a given direction.

Now for the finite case. Imagine a line which passes between $p$ and $q$. Rotating that line around $v$, you will increase one distance while decreasing the other. The change will be greater the farther a point is from the center of location. So you want to distance of the far point to decrease, even if the distance of the near point will increase by a smaller amount in the process. You can keep this argument up until the line actually passes through the far point. So the general solution would be this: compute the Euclidean distances $d(p,v)$ and $d(q,v)$. Obtain $l$ by connecting $v$ to the point wiuth the larger distance, completely ignoring the closer point.

In the corner case of $d(p,v)=d(q,v)$, you can choose the point to connect to arbitrarily. Both $v\times p$ and $v\times q$ will yield the same distance, while any line between them will result in a larger sum of distances. As a line connecting $v$ to either $p$ or $q$ will provide an optimal result for the infinite case as well, you can always choose $l$ to be the connection of $v$ to either of $p$ or $q$, taking care in the choice if the distances are finite and different.

  • 0
    I reverted to the original question and accepted your excellent answer. The new question is [here](http://math.stackexchange.com/questions/263601/find-the-line-closest-ssd-to-2-2d-points-passing-through-a-3rd-point)2012-12-22