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 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)
share|improve this question
    
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
    
@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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

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.