¿Cómo comparar conjuntos de puntos finitos en espacios normados?

Question

Quiero definir una "distancia" entre dos subconjuntos $A, B$ de un espacio normado $(V, \|\cdot\|)$ ambos con (como máximo) $n$ elementos. Una forma sencilla de hacerlo sería definir

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

donde $A = (a_1, \ldots, a_n)$ y $B$ también con $b_i$ . (La imagen a tener en cuenta: encontrar esa coincidencia de puntos en $A$ y $B$ que produce la menor suma de distancia).

Mi pregunta es: ¿se ha hecho ya esto, es decir, es un concepto conocido?

Answer 1

Esto es esencialmente el métrica de transporte , también conocido como Métrica Wasserstein

Answer 2

Véase "Distance Measures for Point Sets and Their Computation" de Thomas Eiter y Heikki Mannila. Dan una lista de varias funciones de distancia entre conjuntos finitos en espacios normados que han aparecido en la literatura, incluyendo la que usted describe que llaman "distancia de suryección" $$d(S_1,S_2)=\min_{\mu}\sum_{e_1e_2\in \mu} \|e_1-e_2\|$$ donde $\mu$ recorre todas las proyecciones del conjunto mayor al otro. Esto se reduce a su definición si los conjuntos tienen igual cardinalidad. Otra generalización es la "distancia de enlace", que considera relaciones arbitrarias en lugar de sólo permutaciones.

Answer 3

Consideremos el grafo bipartito completo $G$ con bipartición $(A,B)$ y que el peso de una arista $ab$ sea $d(a,b)$ . Entonces $d(A,B)$ es simplemente el peso de un emparejamiento perfecto de peso mínimo de $G$ . Encontrar emparejamientos perfectos de peso mínimo es un problema bien estudiado. En particular, podemos calcular $d(A,B)$ en tiempo polinómico. De hecho, incluso en el caso de que los pesos de las aristas no provengan de una métrica, existen algoritmos eficientes. Además, incluso en el caso de que el grafo no sea bipartito, podemos encontrar correspondencias perfectas de peso mínimo en tiempo polinómico. Véase Optimización combinatoria de Cook, Cunningham, Pulleyblank y Schrijver para conocer los sórdidos detalles.

Answer 4

Si sólo se busca alguna forma razonable de definir la distancia de dos $n$ -conjuntos de elementos, nos viene a la mente la distancia de Hausdorff: la distancia de dos conjuntos $A$ y $B$ es el diámetro de su diferencia simétrica $(A\setminus B)\cup(B\setminus A)$ . La distancia de Hausdorff puede utilizarse para comparar pares de conjuntos compactos en un espacio métrico. Esta distancia es en realidad una métrica (en el espacio de subconjuntos compactos de un espacio métrico).