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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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')^2+d(q,q')^2$ 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 squared Euclidean distances of $p$ and $q$ from $l$.

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

(I previously asked a similar question, but here I'd like to minimize the sum of squared distances).

share|cite|improve this question
up vote 1 down vote accepted

Solution 1

Write the line we are looking for as: $ax+by+cz = 0$ (in the projective plane). The purpose is to determine the vectors of coefficients $(a,b,c)$. Since the line can be seen as a point in the dual plane, we shall consider the following normalization: $a^2+b^2+c^2 = 1$.

Then you can formulate the problem as follows: Minimize $d(l,p)^2 + d(l,q)^2$ under the constraints: $av_x + bv_y + cv_z = 0$ and $a^2+b^2+c^2 = 1$.

Now: $d(l,p)^2 = (ap_x +bp_y + c)^2/(a^2 + b^2)$ and $d(l,q)^2 = (aq_x +bq_y + c)^2/(a^2 + b^2)$

Form the lagrangian of optimization problem: $$L(a,b,c,u,v) = \frac{(ap_x +bp_y + c)^2}{a^2 + b^2} + \frac{(ap_x +bp_y + c)^2}{a^2 + b^2} +u(av_x + bv_y + cv_z) + v(a^2+b^2+c^2-1)$$

You need to compute the derivative with respect to $a$, $b$, $c$, $u$, $v$, then multiply by denominator and you get a polynomial system to solve.

Note that the Lagrange multipliers $(u,v)$ are auxiliary unknowns. The second solution avoids introducing these unknowns.

Solution 2:

Take 2 distinct lines $l_1$ and $l_2$ passing through $v$. Then the line we are looking for can be written $l=\alpha l_1 + \beta l_2$.

Express the function to be minimized as a function of $\alpha$ and $\beta$. Take the derivative and you will take a polynomial in $\alpha, \beta$ (it should be homogeneous).

share|cite|improve this answer
Solution 2, seems simpler than solution 1 (though I haven't worked out the equations yet...). Two possible options for $l_1$ and $l_2$ are: (1) the 2 lines passing through $p$ and $q$ and (2) the vertical and horzintal lines passing through $v$. (1) should work regardless of $v$ being at infinity but (2) will add some $0$s to the equations and possibly make them simpler. Can you recommend which 2 line should make the equations more tractable? – Adi Shavit Dec 23 '12 at 7:51

Your Answer


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.