Encontrar una biyección que mejor conserva las distancias

Question

Tengo dos espacios (no necesariamente iguales en dimensión) con N puntos. Estoy tratando de encontrar una biyección (emparejamiento) de los puntos, de modo que las distancias se conserven lo mejor posible.

Parece que no puedo encontrar una discusión de posibles soluciones o algoritmos para esta pregunta en línea. ¿Alguien puede sugerir palabras clave que podría buscar? ¿Este problema tiene un nombre, o aparece en cualquier dominio?

Answer 1

Creo que está buscando un algoritmo Multidimensional Scaling donde se está minimizando el cambio total en la distancia. Desafortunadamente, tengo muy poca experiencia en esta área y no puedo ser de mucha ayuda.

Answer 2

No he oído hablar exactamente del mismo problema. Hay dos tipos de problemas similares:

1. Reducción de dimensionalidad no lineal, se le otorgan N puntos de alta dimensión y desea encontrar N puntos de baja dimensión que conserven la distancia lo mejor posible. MDS, mencionado por Michael Koval es uno de esos métodos.
2. Esto podría ser más prometedor: algoritmos para el problema de asignación. Por ejemplo, Kuhn-Munkres (el algoritmo húngaro), se te da una matriz NxN que codifica el costo de igualar pi con pj y quieres encontrar el costo mínimo de bijection. Hay muchas generalizaciones de este problema, por ejemplo b-matching (Kuhn-Munkres resuelve 1-matching).

Dependiendo de cómo defina "conserva las distancias lo mejor posible" creo que o bien desea (2) o una generalización de (2) de tal manera que el costo no solo dependa de los dos puntos siendo emparejado pero la asignación de todos los otros puntos.

Finalmente, Kuhn-Munkres aparece en todas partes en la investigación de operaciones.