# Find the minimum sum of distances between sets of points to a straight line in a plane

Given $$n$$ dots on a plane, such as: n couples ($$x_i$$,$$y_i$$)
I would like to find a line parallel to y-axis ( $$x=b$$ ), such that the sum of all of the point's distances from that line will be minimal

In order to do that, I need to write an alogrithem with a linear run-time ( $$O(n)$$ )

MY METHOD
I relate only for the $$x$$ values of each point as an element in an Array called $$A$$
So I used the Select(A,left, right, p) & Partition Alogorithm in order to find the median of medians of the array

pseudo-code:

Select(A,left,right,p)
n<-right-left+1
if n=1 then
return A[left]
m<-⌈n/5⌉
let B array with length m
for i <-1 to m
B[i]=medianOf5(A,left,right,x)
x<-Select(B,1,m, ⌈m/2⌉)
q <- partition(A,left,right,x)
k <-q-left+1
if p<k then
return Select(A,left,q,p)
if p>k
return Select(A,q,right,p)


But, using median of medians seems unnecessary
If so, is there an easier way to that? if not ( or if yes for that matter ) was my way correct?
• I think that's correct, and I don't think there is a better way to guarantee $O(n)$ worst case. – Nathaniel Apr 19 at 12:46
• – D.W. Apr 21 at 18:20

Given a line $$L = b$$, the distance from any point $$(x, y)$$ to $$L$$ is $$\left| y - b\right|$$.
The sum of a distances for a set of points $$S = \{(x_1, y_1), \dots, (x_n, y_n)\}$$ is then $$\left| y_1 - b \right| + \cdots + \left| y_n - b \right|$$ which is minimized for which $$b$$?
• But you should take only the $x's$ in order to determine the distance – Omri Braha Apr 19 at 13:56
• And yet, I did not understand, how from that I can determine which is minimized for which $b$ and if my Algorithm has a simpler solution – Omri Braha Apr 20 at 7:26
• @OmriBraha Okay, if it is only two numbers, what do we call the answer then? I.e., you have $\{y_1, y_2\}$. – Pål GD Apr 20 at 7:30