0
$\begingroup$

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) 
  • 0
    @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.2012-06-07

1 Answers 1

2

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