This summer we have presented a new algorithm for matching point sets, with applications in color processing and 3-d point sets registration. This algorithm consists in projecting points on random lines, and then, once the problem has been reduced to one dimension, matching points in 1-d.

When the number of points in both sets is the same, such 1-d matching is trivial: we just need to sort points, and progressively match them from left to right. However, when the number of points is not the same, existing methods are less trivial and much more costly -- typically methods using dynamic programming are used. We have developped an algorithm that is several orders of magnitude faster than such methods. This thus solves a so-called "partial" 1-d optimal transport problem.

We detail this algorithm further in a short article for CNRS: https://ins2i.cnrs.fr/fr/cnrsinfo/apparier-des-points-rapidement-en-les-projetant