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.

Given N points on a 2D grid of the form (X,Y) we need to find to find all the points (R,S) such that the sum of the distances between the point (R,S) and each of the N points given is as small as possible.

Distance measurement b/w 2 points is done as follows

distance between the points (A,B) and (C,D) = |A-C| + |B-D|.

Also :

1) In the N given points some points can be repeated 2) (R,S) can also be any of the N given points 3) All points must have integer co-ordinates.

Constraints: $N \le 1000$, $-10^8 \le X \le10^8$, $-10^8 \le Y \le10^8$

One Such Input is as follows

N = 5

The 5 points are as follows $(0, 0), (-1, 0), (1, 0), (0, 1), (0, -1)$

The number of points (R,S) is 1.

I have written a code for this but for large inputs it times out. I can paste the code here for reference. What i did was to form a polygon that surrounds all of these N points given and within this polygon calculate all the other points for smallest possible distance. But this technique won't work as values of X and Y are huge. Can You suggest me any formula of some sort or any observation so that it becomes easier for me to evaluate this function.

Thanks in advance

share|improve this question

1 Answer 1

For the corresponding problem in one dimension, the solution is to put $R$ at the median of the given numbers; if there are an even number of numbers, then the number of solutions is the number of (integer) medians, which is just the number of integers between the two points on either side of the median, inclusive.

I suspect it's the same in two dimensions: take $R$ to be a median of the $x$-co-ordinates of the given points, and $S$ a median of the $y$-coordinates.

EDIT: more detail, in response to comments.

If you have an odd number of real numbers, $a_1\le a_2\le\cdots\le a_{2n-1}$, then the median is $a_n$.

If you have an even number of real numbers, $a_1\le a_2\le\cdots\le a_{2n}$, then any number $x$ with $a_n\le x\le a_{n+1}$ will serve as a median.

You take your given $N$ points, and you list all the $x$-coordinates; you take $R$ to be any median of these numbers. You list all the $y$-coordinates, and take $S$ to be any median of these numbers.

Now look at the 4-point example in my comment. Since in your problem we are restricted to integer values, $R$, the median of $0,1,4,6$, can be any of the choices $1,2,3,4$; $S$, the median of $0,1,3,5$, can be any of the choices $1,2,3$; all told, then, there are $4\times3=12$ points $(R,S)$ that will do.

I hope that makes the method clear.

share|improve this answer
    
Can you elaborate using a suitable example Gerry Myerson –  AnkitSablok May 5 '12 at 4:11
    
Look at your 5-point example. The $x$-coordinates of the given points are $0,-1,1,0,0$, median zero; the $y$-coordinates are $0,0,0,1,-1$, median zero; so there is a unique $(R,S)=(0,0)$. Suppose you had 4 points, $(0,0),(1,5),(4,1),(6,3)$. The $x$-values are $0,1,4,6$ so $R$ can be anything from 1 to 4, inclusive; the $y$-values are $0,1,3,5$, so $S$ can be anything from 1 to 3, inclusive. –  Gerry Myerson May 5 '12 at 6:35
    
for the case in which there are odd number of points given will the solution be always 1 I am not actually getting the solution you told –  AnkitSablok May 5 '12 at 13:06
    
let us say there N = 5 points (31 , 10 ) (30 , -41 ) ( 20 , 14 ) ( 25 , 18 ) ( 25 , 38 ) how will you evaluate the number of points for this case, just try help me out because with my program I get the answer as 1. and also for this case N = 2 and the points are (0,0) and (1,1) , I get the answer as 4 and N = 6 (1,2)(2,3)(3,4)(4,5)(5,6)(6,7) the answer I get is 4, but how are you evaluating it through your logic. I would be grateful if you can explain the whole process in detail –  AnkitSablok May 5 '12 at 14:06
    
I thought I explained the whole process in detail in my previous comment. But I'll edit something into my answer. –  Gerry Myerson May 5 '12 at 23:57

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.