Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
This is very unclear! The sum of the distances from $g$ to the other points is $3 + 2\sqrt 2 + 2 \sqrt 3$, which is certainly not equal to $9$. Why is the distance from $(x_1,y+1)$ to $(x,y)$ equal to $1$? Try to formulate the problem more clearly. –  TonyK Apr 13 '12 at 20:14
    
@TonyK: OP is not using the usual metric, as he explains. His metric is the maximum of the difference in x and the difference in y. The calculations are correct –  Ross Millikan Apr 13 '12 at 20:21
    
@RossMillikan: Here the distance is not Manhattan Distance, it's Chebyshev Distance But my question is to get the minimum sum of distance of a point from others. We have to choose this specific point from all the given points. Once this specific point is selected, one can calculate the distance easily. But how to choose this specific point. In the above example, the specific point is point g. which gives the sum of minimum distance. –  Ravi Joshi Apr 14 '12 at 14:46
1  
@RaviJoshi: The medians give the optimal point in the plane if you are not restricted to a point within your set. Then I believe you can just look at points which are "close to" that point in your set, but do not know how to make "close to" precise. –  Ross Millikan Apr 14 '12 at 15:07
    
@RossMillikan: From Wikipedia says that The geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. Will this help me? –  Ravi Joshi Apr 14 '12 at 16:41

2 Answers 2

up vote 2 down vote accepted

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).

share|improve this answer
    
@RaviJoshi: Yes, that is right. –  Aryabhata Apr 17 '12 at 18:57
    
(Sorry for deleting the previous comment, i was just trying to edit that comment but getting some error. Please don't mind.)Thanks for the answer. Hey, In Lm formula upper limit of Σ should be n(I am not sure, please check it once). Correct me if i am wrong, For every point i have to calculte the sum of manhattan distances then the minimum sum is the required answer. –  Ravi Joshi Apr 17 '12 at 19:27
    
@RaviJoshi: Actually in $L_m$ the upper limit must be $m$. I will edit. –  Aryabhata Apr 17 '12 at 19:49
    
Yeah. well, as Rm and Lm-1 are related to each other by the equation Rm=Ln-L(m-1). So i need to calculate Ln once. –  Ravi Joshi Apr 17 '12 at 20:05
1  
@RaviJoshi: You need to calculate $L_1, L_2, \dots ,L_n$. And those can be calculated by making one pass over $x_i$. –  Aryabhata Apr 17 '12 at 20:12

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

share|improve this answer
    
This is not the manhattan distance... –  Aryabhata Apr 13 '12 at 19:53
    
@Aryabhata: You are right. This is not manhattan distance. Point (x+1, y+1) is 1 unit far from Point (x, y). –  Ravi Joshi Apr 13 '12 at 19:58
1  
But it is the Manhattan distance rotated $45^\circ$. –  Rahul Apr 13 '12 at 20:02
1  
@RossMillikan: Rahul is right. You can transform the point $(x_n, y_n)$ to $(y_n -x_n, y_n + x_n)$ and get the medians and then transform back. I suggest you edit the answer. –  Aryabhata Apr 13 '12 at 22:12
1  
@RaviJoshi: The median will give an exact point. First transform: $(x_n, y_n) \to (y_n - x_n, x_n + y_n) = (p_n , q_n)$. Find the median of $p_n$, say $p$. THe median of $q_n$ is $q$. Now transform back $(p,q)$ to $((q-p)/2, (q+p)/2)$ and this the point you are looking for. This is an exact point. Do you want the point to be among the original given points? –  Aryabhata Apr 14 '12 at 18:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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