draw line pass a point while minimizing distance with others

Question

I have a set of points (X0,Y0), (X1,Y1)(Xn,Yn). How can I draw a line that pass through (X0,Y0) and have minimum distance with other points (X1,Y1)(Xn,Yn) e,g by matlab, C, fortran etc? Thanks

Answer 1

General equation of line passing through $(x_0,y_0)$ is $y=y_0+k(x-x_0)$, so there is only affecting parameter $k$. We can rewrite this equation like $kx-y+y_0-kx_0=0$. Then distance from point $(x_i,y_i)$ to this line is equal $d_i=\frac{|kx_i-y_i+y_0-kx_0|}{\sqrt{k^2+1}}$. Then sum of distances is equal $D(k)=\frac{\sum_i{|kx_i-y_i+y_0-kx_0|}}{\sqrt{k^2+1}}$. Then the problem transforms to problem of minimization of function of one variable.

If there is no $x_i$ which is equal to $x_0$, then we can limit search of $k$ with interval $k\in [\min \frac{y_i-y_0}{x_i-x_0};\max \frac{y_i-y_0}{x_i-x_0}]$. We can make plot of $D(k)$ with necessary accuracy to find the minimum.

The analytical method of solution is to divide possible $k$ values on regions where $|kx_i-y_i+y_0-kx_0|$ have constant signs. The simplest way to do it is calculation of $k_i=\frac{y_i-y_0}{x_i-x_0}$ and sorting set of $k_i$. Then in any interval $k\in(k_i;k_{i+1})$ between neighboring values of $k_i$ we can expand all $|kx_i-y_i+y_0-kx_0|$ and get linear expression, then in this interval $D(k)=\frac{a_ik+b_i}{\sqrt{k^2+1}}$. Then we can find minimum value $D_i$ of this function in this interval. After calculation of all $D_i$ we can choose minimal $D_i$, corresponding $k$ value is the slope of a sought line.