# How to match two point sets to minimize total distance?

Let's say we have two sets $$X = \{x_1, \ldots, x_n\} \subset \mathbb R^d$$, $$Y =\{y_1,\ldots, y_n\} \subset \mathbb R^d$$, how can we find a permutation $$\pi$$ such that

$$D = \sum_{i=1}^n d(x_i, y_{\pi(i)})$$

is minimal? (Here $$d$$ is some distance function, for simplicity we can assume it is the Euclidean distance, or maybe the squared euclidean distance.)

As far as I remember this is a well studied problem, but can anyone tell me what it is called?

• Take a look at this question and answer: stackoverflow.com/q/52500239/13629726 it seems very similar to your question, so there is a chance this is what you are looking for :) Aug 20, 2021 at 16:36
• @nirshahar Thanks a lot, that's exactly it! Please consider also adding that as an answer! Aug 20, 2021 at 18:57

The planer (d = 2) version of the problem is called in several names such as Euclidean bipartite matching problem, Euclidean bichromatic matching problem, or Bipartite matching of planar points. The fastest known exact algorithm in the real RAM model is the $$O(n^{2+\delta})$$ time ($$\delta > 0$$ is an arbitrary constant) algorithm due to Agarwal et al [1]. There are faster constant-factor approximation algorithms [2]. There is a sub-quadratic algorithm if the coordinates are bounded integers [3].