<p>After asking around a bit on Twitter, I found that what you're trying to solve seems to be an instance of the <a href="https://en.wikipedia.org/wiki/Assignment_problem" rel="nofollow">assignment problem</a>. In general, the assignment problem is to take two sets and assign elements of one to the other, in such a way that a cost function is minimized.</p>

<p>In your case the two sets would be the stars in each galaxy, and the cost function would be the distances between stars. An optimal solution to the assignment problem would then minimize the total distance between corresponding stars, summed over all the stars in the galaxies.</p>

<p>A classic algorithm for solving the assignment problem is called the <a href="https://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow">Hungarian algorithm</a>. If you google around, you'll some explanations of how it works. There's even a Python module implementing this algorithm, called <a href="http://software.clapper.org/munkres/" rel="nofollow">Munkres</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2016-09-05T03:02:35.950Z
2016-09-05T03:02:35.950Z
Nathan Reed
<p>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 <a href="https://codereview.stackexchange.com/questions/140292">here</a>.</p>

<p>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...</p>

<p>star 0: [4, 1, 0, 3, 2]</p>

<p>star 1: [2, 0, 4, 3, 1]</p>

<p>star 2: [2, 1, 3, 0, 4]</p>

<p>star 3: [0, 3, 2, 4, 1]</p>

<p>star 4: [0, 3, 1, 4, 2]</p>

<p>from these lists default first neighbour list:</p>

<p>star 0: [4]</p>

<p>star 1: [2]</p>

<p>star 2: [2]</p>

<p>star 3: [0]</p>

<p>star 4: [0]</p>

<p>Since I want unique neighbour in GalaxyB, but here you see a problem, star 2 in GalaxyB is closest to two GalaxyA stars 1 &amp; 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.</p>

<p>after applying unique neighbour algorithm first neighbour list will be:</p>

<p>star 0: [4]</p>

<p>star 1: [2]</p>

<p>star 2: [1]</p>

<p>star 3: [3]</p>

<p>star 4: [0]</p>

CC BY-SA 3.0
2016-09-02T21:53:15.507Z
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
CC BY-SA 3.0
2016-09-04T10:13:16.240Z
Yes, please check edit.
PradeepBarua
CC BY-SA 3.0
2016-09-04T22:13:32.713Z
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 is on Codidact now
CC BY-SA 3.0
2016-09-04T22:21:45.593Z
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 is on Codidact now
CC BY-SA 3.0
2016-09-05T04:59:54.327Z
@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
<performance>
How to get unique nearest neighbour?
PradeepBarua
# How to get unique nearest neighbour?

(Asked by: username_0 on 2016-09-02)

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](https://codereview.stackexchange.com/questions/140292).

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]

**Tags:** performance

> **Comments:**
> **username_1**: 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?  
> **username_0**: Yes, please check edit.  
> **username_2**: 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?  
> **username_2**: 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?  
> **username_0**: @username_2: 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.  

---

## 1 answers

### Answer by username_1 on 2016-09-05. Score: 1

After asking around a bit on Twitter, I found that what you're trying to solve seems to be an instance of the [assignment problem](https://en.wikipedia.org/wiki/Assignment_problem). In general, the assignment problem is to take two sets and assign elements of one to the other, in such a way that a cost function is minimized.

In your case the two sets would be the stars in each galaxy, and the cost function would be the distances between stars. An optimal solution to the assignment problem would then minimize the total distance between corresponding stars, summed over all the stars in the galaxies.

A classic algorithm for solving the assignment problem is called the [Hungarian algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm). If you google around, you'll some explanations of how it works. There's even a Python module implementing this algorithm, called [Munkres](http://software.clapper.org/munkres/).

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.


---

