# The Nearest Points

Given a set R of N points R={(x1,y1,z1),(x2,y2,z2),.....,(xn,yn,zn)} and set S of M points S={ ((a1,b1,c1),(a2,b2,c2),...(am,bm,cm))}.

for each point pi(i=1 to N) in Set R ,find the point qj(j=1 to m) in set S such that the euclidean distance between pi and qj is minimum.

Note. euclidean distance between (l1,m1,n1) and (l2,m2,n2)=(sqrt) abs(l1-l2)^2+abs(m1-m2)^2+abs(n1-n2)^2.

The constraints are large .The total number of points in each set R and S is very large (1<=N,M<=50,000).

How to solve this problem..

Edit

*Ross Millikan pointed out this can be done in polynomial time.(So i had made a slight change in the problem statement). By brute force it can be done in O(N*M) time .But the problem is (N*M) means (50000*50000)=10^8 steps .But i have to get output in less than 3 seconds.So,is there better solution than O(N*M).*

Thanks!

for example::

The points of Set S {(1,0,0),(0,0,1),(0,1,0),
The points of Set R {(0,-1,0),(0,0,-1),
For the point p: (0 ,-1 ,0) in set R

Eucd distance between point p and (1,0,0) is: sqrt(2)
Eucd distance between point p and (0,0,1) is: sqrt(2)
Eucd distance between point p and (0,1,0) is: sqrt(4)
So minimum distance is (sqrt)2
So the point ie .Answer= q= (0 ,0 ,1)

For the point p: (0 ,0 ,-1) in set R

Eucd distance between point p and (1,0,0) is: sqrt(2)
Eucd distance between point p and (0,0,1) is: sqrt(4)
Eucd distance between point p and (0,1,0) is: sqrt(2)
So minimum distance is (sqrt) 2
So the point ie .Answer= q=  (0 ,1 ,0).

Note ,if there are more than one points for which the distance is minimum,we just need any one of them.

Example 2:

The points of Set S {(-91,10,5),(3,-6,7),(4,5,8),(-89,1,4),
The points of Set R {(4,-6,7),(10,-30,17),(8,9,10),(3,4,-9),
For the point p: (4 ,-6 ,7) in set R

Eucd distance between point p and (-91,10,5) is:(sqrt) 9285
Eucd distance between point p and (3,-6,7) is:(sqrt) 1
Eucd distance between point p and (4,5,8) is:(sqrt) 122
Eucd distance between point p and (-89,1,4) is:(sqrt) 8707
So minimum distance is (sqrt) 1
So the point ie .Answer= q= (3 ,-6 ,7)
For the point p: (10 ,-30 ,17) in set R

Eucd distance between point p and (-91,10,5) is:(sqrt) 11945
Eucd distance between point p and (3,-6,7) is:(sqrt) 725
Eucd distance between point p and (4,5,8) is:(sqrt) 1342
Eucd distance between point p and (-89,1,4) is:(sqrt) 10931
So minimum distance is  (sqrt)725
So the point ie .Answer= q= (3 ,-6 ,7)
For the point p: (8 ,9 ,10) in set R

Eucd distance between point p and (-91,10,5) is:(sqrt) 9827
Eucd distance between point p and (3,-6,7) is:(sqrt) 259
Eucd distance between point p and (4,5,8) is:(sqrt) 36
Eucd distance between point p and (-89,1,4) is:(sqrt) 9509
So minimum distance is  (sqrt)36
So the point ie .Answer= q= (4 ,5 ,8)
For the point p: (3 ,4 ,-9) in set R

Eucd distance between point p and (-91,10,5) is:(sqrt) 9068
Eucd distance between point p and (3,-6,7) is:(sqrt) 356
Eucd distance between point p and (4,5,8) is:(sqrt) 291
Eucd distance between point p and (-89,1,4) is:(sqrt) 8642
So minimum distance is  (sqrt) 291
So the point ie .Answer= q= (4 ,5 ,8)
-
This is solvable in polynomial time: For each of The $N$ points $p_i$, calculate the $M$ distances from the $q_j$ and sort them. This is of order $NM \log M$. Do you mean that you can't reuse one set of points? –  Ross Millikan Jun 7 '12 at 4:34
@Ross Millikan:: I can reuse them.How it can be done in NMlogM time? –  Maths123 Jun 7 '12 at 4:40
@RossMillikan:: By brute force it can be done in N*M times .We don't require MlogM approach.. But the problem is N*M means (50000*50000)=10^8 steps ..But i have to get output in less than 4 seconds.. What i exactly Want is better solution than O(N*M) –  Maths123 Jun 7 '12 at 4:46
Would you like to do something about that 29 percent accept rate? –  Gerry Myerson Jun 7 '12 at 6:26
@ChopraJack: yes, you can find the highest in M tries. That shows this problem is not in $NP$. But even problems in $P$ can be intractable if the number of cases is large enough. –  Ross Millikan Jun 7 '12 at 13:11

You can treat this as $n$ independent nearest neighbour search problems, namely, for each point in $R$, find its nearest neighbour among the $m$ points in $S$. The Wikipedia article lists lots of methods to do this efficiently. A popular approach is to use a $k$-D tree on the points in $S$. This takes $O(m\log m)$ time to build, and $O(\log m)$ time per nearest neighbour query if the points are randomly distributed. This gives a total time of $O((m+n)\log m)$.