6
$\begingroup$

I want to find the minimum sum of distances of a point(x, y) from other points which lies in the x-y plane. There are 8 cells which are 1 unit far from any given cell. Here distance between two points is not meant to calculate manhattan distance between those points. Here point (x+1, y+1) is 1 unit far from point (x, y)Example Image to describe the distance between two points. In the above diagram point, point p is 4 unit far from point t. Since there are 4 cells between p and t. Point s is 2 unit far from point p. Since there are two cells between p and s.
The point from where I want to find the sum of distance is one of the points which lies in the x-y plane is one, which gives the minimum sum of distances.
Example image of points lying in x-y plane For example. In the above example image, point g(3,2) is in the minimum distance from all other points. The resultant distance is 2(a-g)+ 1(b-g)+ 2(c-g)+ 1(d-g)+ 1(e-g)+ 2(f-g)=9. My objective is to find the minimum sum of distances of a point, which is 9 in this example. Thank you.

To find out the minimum sum of distances, my idea is is get that point first, which is close to all other points. Once i get the point, i can get the distance from all points to that point and finally sum up. But i don't know how can i get the point which is close to all other points.

  • 0
    okay. So first i should calculate `(x1+x2+x3+x4...+xn)/n` and `(y1+y2+y3+y4...+yn)/n` . This will give me center point. Then i have to find nearest point somehow.2012-04-14

2 Answers 2

3

Since you want a point from the given points (based on your comments to Ross' answer) here is an $O(n \log n)$ time algorithm, based on the idea of rotating by $45^{\circ}$ and using the equivalence with Manhattan Distance. This only works for the 2D plane.

Assume the points are $(p_n, q_n)$. You transform them to $(q_n - p_n, q_n + p_n) = (x_n , y_n)$ say.

Now we will see how to compute the $x$ component of the Manhattan distance for each point in $O(n \log n)$ time.

We will assume that $x_1 \lt x_2 \lt ...\lt x_n$. This can be done by sorting them. Also, the algorithm can be modified to deal with the case when they are not distinct. For simplicity, we assume they are unique.

Define $L_m = \sum_{j=1}^{m} x_j$ and $R_m = \sum_{j=m}^{n} x_j$. Note that $R_m = L_n - L_{m-1}$. (Define $L_{0} = 0$)

Note that the $L_i$ and $R_i$ can be computed in $O(n)$ time, by looping through the array and maintaining the cumulative sum.

Now for a given $x_k$ we have that $\sum_{j=1}^{n} |x_k - x_j| = \sum_{j=1}^{k-1} (x_k - x_j) + \sum_{j=k+1}^{n} (x_j - x_k) = R_{k+1} - L_{k-1} - (n-2k+1)x_k$

(This is where we used the distinctness assumption, but can be modified easily to deal with it).

Similarly do with $y_k$.

Thus we can compute the sum of (manhattan) distances for each point to other points in total $O(n)$ time.

Finding the minimum among them is another $O(n)$ (or just keep track while computing the distances).

  • 0
    @deep: Can you be more speci$f$ic?2012-09-05
3

If you are not restricted to the origin being one of your points, you want to transform the points $(x_i,y_i)$ to $(x_i+y_i,x_i-y_i)$, take the median of all the transformed coordinates to get $(x'_m,y'_m)$, then transform back to $(\frac{x'_m+y'_m}2,\frac{x'_m-y'_m}2)=(x_m,y_m)$. This is explained a bit under "An optimality property". If you are restricted to one of your points, you need to look around a bit, but that gives a starting point.

Added: this has been corrected for the metric in use instead of the Manhattan metric

  • 0
    @RaviJoshi: I have added an answer.2012-04-17