# The Nearest Points

Given a set $R$ of $N$ points $R={(x_1, y_1, z_1), (x_2, y_2, z_2),....., (x_n, y_n, z_n)}$ and set $S$ of $M$ points $S={ ((a_1, b_1, c_1), (a_2, b_2, c_2),...(a_m, b_m, c_m))}$.

for each point $p_i(i=1\space \text{to}\space N)$ in Set $R$, find the point $q_j(j=1\space \text{to}\space m)$ in set S such that the euclidean distance between $p_i$ and $q_j$ is minimum.

Note: euclidean distance between $(l_1, m_1, n_1)$ and $(l-2, m_2, n_2)$$=\sqrt{ abs(l_1-l_2)^2+abs(m_1-m_2)^2+abs(n_1-n_2)^2}$.

The constraints are large. The total number of points in each set $R$ and $S$ is very large $(1\leq N, M\leq 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 NM times .We don't require MlogM approach.. But the problem is NM 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
@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)$.