Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $<l\equiv p' \times q', v> = 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$.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Good answer! I was expecting an algebraic answer, and you gave an intuitive geometric one. You were right in your comment, I'd actually like to minimize the sum of squared distances. How does this change affect the solution? –  Adi Shavit Dec 21 '12 at 19:40
    
@AdiShavit, it changes the answer completely. Look for existing material on that topic, and ask a new question if you can't find a solution to that yourself. –  MvG Dec 21 '12 at 21:50
    
I reverted to the original question and accepted your excellent answer. The new question is here –  Adi Shavit Dec 22 '12 at 8:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.