1

Say I have two matrices of points, A and B, that contain point coordinates. I want to find the point pairs that minimize the sum of euclidean differences between points pairs.

For instance, in the 1-D case, I have: A = [4 1 1.5]; B = [4 1.2 0]; If the algorithm matches the nearest pairs first (like this one), this could return pairs [4 4], [1 1.2], [1.5 0]. This would give a total difference of 1.5+.2+0 = 1.7.

I'm looking for a solution that would minimize the total difference between pairs, which gives the solution [4 4], [1 0], [1.5 1.2], for a total difference of .3+1+0 = 1.3.

This is for 10k-100k points in 3D.

Thanks for your help!

M Kurla
  • 21
  • 4
  • 1
    Look for RANSAC and ICP. Those are the most popular method I believe. – Cris Luengo Sep 13 '18 at 00:11
  • This appears to be a variant of the [assignment problem](https://en.wikipedia.org/wiki/Assignment_problem). It can be solved using the [Hungarian algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm) although even with what appears to be an efficient implementation [provided here](https://www.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems-v2-3) I estimate the 10,000 x 10,000 case will take about 10 hours and the 100k x 100k case will take about 1.2 years. You may want to look for an approximate greedy approach. – jodag Sep 13 '18 at 04:13
  • 1
    @jodag the Hungarian algorithm solves the assignment problem without relying on any knowledge of dependencies between pairwise distances. Because in this variant of the problem all distances are Euclidean there's good reason to expect to be able to do better. There seems to be some literature around referring to it as Euclidean bipartite matching or the Euclidean assignment problem, but this didn't immediately lead to any nice accessible algorithm implementation I could find. – Will Sep 13 '18 at 14:59
  • @Will Thanks for the info. I looked around for a while and found [Agarwal, Pankaj K., Alon Efrat, and Micha Sharir. "Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications." (2006).](http://www.cs.tau.ac.il/~michas/shallowvd.pdf) It looks like there's an `O(n^(2+eps))` algorithm presented in Section 7 but I couldn't find an implementation. – jodag Sep 13 '18 at 16:30
  • I would love to see how far off what I propose is. (Following what @jordag said). Could you post your implementation and an example list of points please. – PilouPili Sep 14 '18 at 07:00

2 Answers2

1

Thanks everyone for your comments! And particularly @jodag for identifying this as the assignment problem, giving the Hungarian algorithm as a solution, and providing a link to a Matlab implementation.

This seems to be working, for a low number of particles at least. If I get bogged down, I'll try dividing the search area.

M Kurla
  • 21
  • 4
0

I don't know if you need an answer limited to Matlab (because I haven't seen any Matlab function to do spatial index) but here goes.

You can use https://www.boost.org/doc/libs/1_68_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree.html to "spatial index your nodes" (https://en.wikipedia.org/wiki/Spatial_database#Spatial_index)

The aim is to be able to search the closet node in O(log(N)) N being the number of nodes

Suppose you have your two sets A and B both containing N nodes

indexing A and B costs O(N log(N)) and O(N log(N))

picking point i in A you search in RTree(B) you find point j. store d1 (distance between i andj) (that search cost O(log(N))

picking point j in B you search in RTree(A) if you find point i then you have got your match [i in A with j in B] if you get node k then calculate the distance d2

if d2 < d1 your match is [k in A with j in B] else your match is [i in A with j in B]

do that for all N points

overall cost something in O(N log(N))

PilouPili
  • 2,601
  • 2
  • 17
  • 31
  • This is just iteratively finding nearest neighbors which OP pointed out doesn't necessarily give pairs with minimum total pair-wise distance. – jodag Sep 14 '18 at 02:23