3
$\begingroup$

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]

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – Nathan Reed
    Sep 2, 2016 at 21:53
  • $\begingroup$ Yes, please check edit. $\endgroup$
    – PradeepBarua
    Sep 4, 2016 at 10:13
  • $\begingroup$ 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? $\endgroup$
    – trichoplax is on Codidact now
    Sep 4, 2016 at 22:13
  • $\begingroup$ 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? $\endgroup$
    – trichoplax is on Codidact now
    Sep 4, 2016 at 22:21
  • 1
    $\begingroup$ @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. $\endgroup$
    – PradeepBarua
    Sep 5, 2016 at 4:59

1 Answer 1

Reset to default
1
$\begingroup$

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. 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. If you google around, you'll some explanations of how it works. There's even a Python module implementing this algorithm, called 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.