Viabilidad de una lista de distancias prescritas en R^3

Question

Estoy desconcertado con el siguiente problema:

Dado $n$ números reales es obtener una respuesta Sí/No: "si es posible ordenar diferentes puntos en la escala euclidiana $\mathbb{R}^3$ de modo que cada uno de los números dados represente una distancia más corta que pertenezca a un par de puntos distintos?".

¿Cuál es un algoritmo eficaz para resolver este problema? Si entiendo bien, primero tengo que encontrar $m$ de $n=\frac{m(m+1)}{2}$ que es el número de tales puntos. Pero, ¿cuál es el siguiente paso? ¿Debo ocuparme de comprobar la desigualdad de los triángulos (lo que parece muy poco eficiente) o qué?

Gracias de antemano.

Answer 1

Lo que no parece haber sido mencionado en este viejo hilo es que se trata de un problema bien estudiado que recibe el nombre de _geometría de la distancia_ , que Wikipedia define como "la caracterización y el estudio de conjuntos de puntos basados únicamente en valores dados de las distancias entre pares de miembros". El problema tiene aplicaciones especialmente a la estructura molecular. Crippen y Havel publicaron un libro sobre este tema en 1988: Geometría a distancia y conformación molecular (Research Studies Press, Taunton, Somerset, Inglaterra), con una actualización posterior a cargo de Crippen (" Geometría de la distancia química: Realización actual y proyección futura "). Hay muchos artículos sobre el tema, publicados en lugares como el Revista de Química Computacional por ejemplo, "Molecular conformations from distance matrices" ( Volumen 14, número 1, páginas 114-120, enero de 1993 ). Debido a las numerosas aplicaciones, existen paquetes de software desarrollados para resolver el problema; el artículo de Wikipedia tiene una lista . El problema es intratable desde el punto de vista computacional; la prueba de que una versión es NP-difícil se remonta a a un artículo de Saxe de 1979, "Embeddability of weighted graphs in $k$ -es fuertemente NP-difícil".

Answer 2

Nos deja etiquetar los puntos de $x_0,x_1,\dots,x_m$. Para cada par $(x_i,x_j)$ prescribir el valor de la lista; denota por decir $d(x_i,x_j)$. Si no hay repeticiones, a continuación, todos juntos tienen $N=[m{\cdot}(m+1)]!$ maneras de hacer esto.

Tenga en cuenta que $d(x_i,x_j)$ completamente determinar "$m\times m$-matriz de productos escalares" $$a_{ij}=\tfrac12\cdot[d^2(x_0,x_i)+d^2(x_0,x_j)-d^2(x_i,x_j)].$$

Usted tiene que responder a dos preguntas para cada una de obtenerse $N$ matrices:

• $(a_{ij})$ define un no-negativo de la forma cuadrática

• $\mathop{\rm rank}(a_{ij})\leqslant 3$.

Si por una matriz de las respuestas son SÍ a ambas, a continuación, la respuesta a tu pregunta también es SÍ (y viceversa).

Answer 3

La respuesta de Antón incluye los dos aspectos siguientes del problema:

• Primero hay que decidir (o que te den) la estructura combinatoria del grafo que quieres incrustar, es decir, asignar de alguna manera las n distancias a los n pares de puntos. Habrá algunas simetrías, pero no las suficientes como para evitar este paso; incluso cuando m = 4, n = 6, hay que decidir qué pares de aristas del tetraedro serán opuestas.

• Una vez hecho esto, comprobar la desigualdad del triángulo para todos los triples de puntos no es suficiente. Por ejemplo, consideremos 5 puntos en R 4 que no se encuentran en un hiperplano. La 10-tupla de distancias entre estos puntos determina el conjunto de 5 puntos hasta un movimiento rígido (o reflexión) de R 4 . En particular, no podemos encontrar 5 puntos en R 3 con las distancias prescritas entre pares. Sin embargo, es evidente que se cumplen todas las desigualdades triangulares.

Answer 4

Creo que el siguiente documento aborda esta cuestión:

Espacios métricos y funciones definidas positivas por: I. J. Schoenberg Transactions of the American Mathematical Society, Vol. 44, No. 3. (nov 1938), pp. 522-536.

Hay un libro de artículos de Schoenberg en google books y si buscas el título deberías poder leer este artículo.

Answer 5

No es una respuesta completa, pero puede arrojar algo de luz sobre lo que está en juego.

Sea $n=m(m-1)/2$ y digamos que has decidido qué pares de la $m$ puntos debe obtener cuál de los $n$ distancias. Debe formar el $m\times m$ matriz $M$ cuyas entradas son las distancias al cuadrado, es decir, $M\_{ij}=||x\_i-x\_j||^2$ donde el $m$ puntos (desconocidos) son $x\_1,\ldots,x\_m$ . Supongamos que el $m$ puntos pertenecen todos a $\mathbb{R}^k$ . Sea $X$ sea el $k\times m$ cuya matriz $j$ -ésima columna es $x\_j$ . Sin pérdida de generalidad, los puntos tienen media cero, por lo que $x\_1 + \ldots + x\_m = X\alpha^T = 0$ donde $\alpha=(1,\ldots,1)$ . Es fácil demostrar que si $P=I-\frac1m\alpha \alpha^T$ es la proyección ortogonal sobre el complemento ortogonal de $\alpha$ entonces $PMP = -2X^TX$ . Por lo tanto, una vez que sepa $M$ puede intentar encontrar $X$ mediante una modificación de la descomposición de Cholesky aplicada a $-\frac12PMP$ . Es necesario modificar el procedimiento para que devuelva un $k\times m$ matriz, no una $m\times m$ matriz. (Puesto que desea $\mathbb{R}^3$ , debe tomar $k=3$ .) Si tiene éxito, entonces usted tiene una solución; de lo contrario, no existe ninguna solución.

Desgraciadamente, eso supone que has asignado la función $n$ distancias a pares de puntos ya. Si el procedimiento anterior falla, es posible que otra asignación de distancias a pares dé una solución. No veo ninguna manera fácil de resolver esto; comprobar todas las asignaciones posibles está fuera de cuestión incluso para valores bastante modestos de $m$ aunque se puedan romper todas las simetrías, ya que creo que habría que comprobar $(m(m-1)/2)!/m!$ asignaciones en el peor de los casos. Tal vez haya una forma de reducir el número de permutaciones que hay que comprobar, pero no la veo.