0
$\begingroup$

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?
$\endgroup$
2
1
$\begingroup$

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$?

$\endgroup$
4
  • $\begingroup$ But you should take only the $x's$ in order to determine the distance $\endgroup$ – Omri Braha Apr 19 at 13:56
  • $\begingroup$ @omribraha that doesn't make much of a difference, but yes, of it's a vertical line, you pick the xs. $\endgroup$ – Pål GD Apr 19 at 14:19
  • $\begingroup$ 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 $\endgroup$ – Omri Braha Apr 20 at 7:26
  • $\begingroup$ @OmriBraha Okay, if it is only two numbers, what do we call the answer then? I.e., you have $\{y_1, y_2\}$. $\endgroup$ – Pål GD Apr 20 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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