1
$\begingroup$

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

1 Answers 1

2

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.

  • 0
    Can you elaborate using a suitable example Gerry Myerson2012-05-05
  • 0
    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.2012-05-05
  • 0
    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 told2012-05-05
  • 0
    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 detail2012-05-05
  • 0
    I thought I explained the whole process in detail in my previous comment. But I'll edit something into my answer.2012-05-05
  • 0
    "I suspect it's the same in two dimensions" Surely it is2012-05-06
  • 0
    @leonbloy, yes, I wasn't 100% sure when I first posted, but now it seems pretty straightforward.2012-05-06
  • 0
    @Gerry Myerson and Leonboy can you give me some links where I can study this problem or something related to this problem2012-05-06
  • 0
    Discussion of the 1-dimensional problem at http://www.medicine.mcgill.ca/epidemiology/hanley/Reprints/median-elevator.pdf. General question discussed at http://stackoverflow.com/questions/10418654/all-points-with-minimum-manhattan-distance-from-all-other-given-points-optimize2012-05-07