How to compare finite point sets in normed spaces?

Question

I want to define a "distance" between two subsets $A, B$ of a normed space $(V, \|\cdot\|)$ both with (at most) $n$ elements. A straightforward way for me to do this would be to define

$$ d(A, B) := \min_ {\pi\in S_n}\\ \sum_{i=i}^n \|a_i - b_{\pi(i)}\| $$

where $A = (a_1, \ldots, a_n)$ and $B$ likewise with $b_i$. (The image to have in mind: find that matching of points in $A$ and $B$ that produces the smallest distance sum.)

My question is: Has this already been done, i. e. is this a well-known concept?

Answer 1

This is essentially the transportation metric, also known as Wasserstein metric

Answer 2

See "Distance Measures for Point Sets and Their Computation" by Thomas Eiter and Heikki Mannila. They give a list of various distance functions between finite sets in normed spaces that have appeared in literature, including the one you describe which they call "surjection distance" $$d(S_1,S_2)=\min_{\mu}\sum_{e_1e_2\in \mu} \|e_1-e_2\|$$ where $\mu$ runs through all surjections from the bigger set to the other. This reduces to your definition if the sets have equal cardinality. Another generalization is the "Link distance" which considers arbitrary relations instead of just permutations.

Answer 3

Consider the complete bipartite graph $G$ with bipartition $(A,B)$, and let the weight of an edge $ab$ be $d(a,b)$. Then $d(A,B)$ is simply the weight of a minimum weight perfect matching of $G$. Finding minimum weight perfect matchings is a well-studied problem. In particular, we can compute $d(A,B)$ in polynomial-time. Indeed, even in the case that the edge weights do not come from a metric, efficient algorithms exist. Also, even in the case that the graph is not bipartite, we can find minimum weight perfect matchings in polynomial-time. See Combinatorial Optimization, by Cook, Cunningham, Pulleyblank, and Schrijver for the sordid details.

Answer 4

If you just look for some reasonable way to define the distance of two $n$-element sets, the Hausdorff distance comes to mind: the distance of two sets $A$ and $B$ is the diameter of their symmetric difference $(A\setminus B)\cup(B\setminus A)$. The Hausdorff distance can be used to compare pairs of compact sets in a metric space. This distance is actually a metric (on the space of compact subsets of a metric space).