Given a set of $n$ points $p_1,p_2,\ldots,p_n$ on a horizontal straight line (not necessarily in the order from left to right) with associated $x$-coordinates $x_1,x_2,\ldots,x_n$ (not necessarily in ascending orders) and associated weights $w_1,w_2,\ldots,w_n$ such that $\sum_{i=1}^n w_i = 1$. The objective is to find a point $p$ on the straight line such that the sum $\sum_{i=1}^n |x_p-x_i|w_i$ is minimum, where $x_p$ is the $x$-coordinate of $p$.
Prove that the sum $\sum_{i=1}^n |x_p-x_i|w_i$ is minimum at a point $p$, where $p$ is such that $\sum_{x_i<x_p} w_i < \frac{1}{2}$ and $\sum_{x_i>x_p} w_i \leq \frac{1}{2}$.
I am trying to use algorithm Select to prove it. The algorithm divides the x-coordinates into $[n/5]$ sublists such that first $[n/5]-1$ sublists contain exactly 5 elements each, while the remaining one contains $n \pmod 5$ elements. Then we find the median of each sublist. Repeat the same process for each sublist.
But I think I get the gist of the problem, I think it is sufficient to prove that if $q$ is any point on the line such that $q≠p$,then $\sum_{i=1}^n|x_q-x_i| w_i≥\sum_{i=1}^n|x_p- x_i | w_i$, where $x_q$ is the x-coordinate of $q$.
But I am going no where with this. Am I using the wrong approach? Should I be using algorithm Min to get this? If yes, can someone explain how to get it?
