# How to get unique nearest neighbour?

There's already something called K-nearest neighbour algorithm with gives nearest neighbour to points. But what I want is unique neighbour which is not shared by any other neighbour. I've implemented this logic but it's very slow. You can review my code here.

EDIT: Let's assume there're 2 galaxies with 5 stars in each. GalaxyA neighbour list(let's call it closestNeighbourList) in GalaxyB starting from closest to fartherest...

star 0: [4, 1, 0, 3, 2]

star 1: [2, 0, 4, 3, 1]

star 2: [2, 1, 3, 0, 4]

star 3: [0, 3, 2, 4, 1]

star 4: [0, 3, 1, 4, 2]

from these lists default first neighbour list:

star 0: [4]

star 1: [2]

star 2: [2]

star 3: [0]

star 4: [0]

Since I want unique neighbour in GalaxyB, but here you see a problem, star 2 in GalaxyB is closest to two GalaxyA stars 1 & 2 and same for star 0. So these are not unique neighbour as shared by two or more stars. So to overcome this problem what I'm doing first storing all neighbours in a list(closestNeighbourList) then looping over those to check if it's closer to(shared by) some other star then go to next neighbour and when it's find unique neighbour break out of the loop.

after applying unique neighbour algorithm first neighbour list will be:

star 0: [4]

star 1: [2]

star 2: [1]

star 3: [3]

star 4: [0]

• Can you expand the question a bit? Clarify what you mean by "not shared by any other neighbour", and discuss how your current algorithm works? Looking at your other question it sounds like you have two clouds of points and you want to put them into 1:1 correspondence, so each point in cloud A is matched to exactly one in cloud B and vice versa. And you want the matched pairs of points to be close to each other. Is that right? – Nathan Reed Sep 2 '16 at 21:53
• Yes, please check edit. – PradeepBarua Sep 4 '16 at 10:13
• The link you give to the code on Code Review.SE appears to be a question asking the same thing. Are you looking for the same thing from Computer Graphics.SE (a review of how to optimise for speed) or are you asking whether there is a different algorithm that gives different but acceptable results? – trichoplax Sep 4 '16 at 22:13
• Do you just need a 1 to 1 pairing of points from set A with points from set B, or do you require the pairing that has the shortest possible total length? – trichoplax Sep 4 '16 at 22:21
• @trichoplax: I'm looking for another algorithm to make it faster. I need 1:1 pairing with shortest possible distance. My code is already working but it's too slow. – PradeepBarua Sep 5 '16 at 4:59

A warning: this algorithm runs in $O(n^3)$ time, so it will be rather slow for large point sets. You might want to do some further research on fast algorithms for the assignment problem. It may be that you can find a faster, approximate algorithm if you don't require a perfectly optimal solution. Or maybe there are specialized algorithms for the case of point clouds that can do better.