Definir las posiciones de un conjunto de puntos dado (sólo) las distancias entre ellos

Question

He estado pensando espacial se transforma.

Dado $n$ puntos, hay $\frac{n!}{(n-2)!2!}$ combinaciones de la selección de dos puntos, por lo que para 64 puntos en el espacio, hay 2016 único punto-a-punto las relaciones (por ejemplo, las distancias entre los puntos involucrados).

Puede un conjunto de puntos definida únicamente por el correspondiente conjunto completo de relaciones. Es decir, si tuviera puntos a,B y C, podría derivar de un único punto de arreglos para satisfacer una lista de distancias, AB, AC, BC. Podría hacer esto en general para cualquier lista de punto a punto distancias indicadas $n$ puntos? ¿Cómo se hace?

Entiendo que dado que sólo la posición relativa, la colocación de los puntos en un sistema de coordenadas absoluto es imposible. Entiendo también, que con pocos puntos, por ejemplo, 2,3.., la solución no es única - pero, ¿qué acerca de los números más grandes?

Editar - Adición de una restricción física.

Vamos a definir un 16 por 16 por 16 cuadrícula $G$, basado en el sistema de coordenadas Cartesianas. Permítanos calcular o definir un conjunto de distancias $D_R$, que representan la distancia física entre los puntos en $G$. Si tenemos una buena función continua sin una singularidad - para representar gradiente en el espacio, por ejemplo - entonces podríamos corregir nuestros distancia $D_R$, a cierta distancia efectiva $D_E$, por multiplicar cada distancia por el gradiente medio, por ejemplo. La tarea es definir los puntos en una "Distancia Eficaz del Espacio". Mi punto es que en la realidad física hay restricciones sobre los conjuntos de distancias - no puedo esperar para encontrar una solución a un conjunto arbitrario de las distancias. ¿Esto de cambiar las cosas?

Answer 1

Esto en general no es posible.

Primero de todos, cualquiera que sea la solución que usted consiga no va a ser único, como usted indica, en el sentido de que las traslaciones y rotaciones del conjunto de puntos también ser una solución para el problema. Más allá de eso, hay dos posibles peligros:

• El conjunto de las "distancias" puede ser inconsistente si se configura mal. Al menos se debe cumplir con todas las desigualdades de los triángulos de la forma $d_{AB}+d_{BC}\leq d_{AC}$; si no, entonces no hay posibilidad de una realización.
• También puede no ser realizable en tres dimensiones. El ejemplo más simple de esto es cinco puntos equidistantes. Cuatro puntos de ajuste en los vértices de un tetraedro, pero para adaptarse a un quinto punto, usted necesita una de cuatro dimensiones simplex tener la incrustación se desea. Esto generalmente será el caso: un conjunto coherente de las distancias entre las $n$ puntos puede ser realizado en $n-1$ dimensiones, pero no hay ninguna garantía de menores dimensiones realizaciones.

En general, esto es lo que pasa si te dan un conjunto de tales distancias entre el $n$ puntos.

• Primero se comprueba que son consistentes. Si no, entonces usted puede dar de inmediato.#

• Si es así, entonces empieza a trabajar en $n-1$ dimensiones. Colocar el primer punto donde sea. Elige tu segundo punto en cualquier lugar de la $(n-2)$-dimensiones hypersphere que es la distancia correcta $d_{12}$ distancia. El tercer punto debe ser $d_{13}$ lejos de la primera y $d_{23}$ a partir del segundo, así que se acuesta en la $(n-3)$-dimensiones de la intersección de dos $(n-2)$-dimensiones hyperspheres. Esto se mantiene: el $k$th punto estarán en $k-1$ restricciones y puede por lo tanto se encuentran en cualquier lugar en un $(n-1)-(k-1)=(n-k)$-dimensional de la hipersuperficie. Al final, su segundo a último momento se encuentran en un círculo, y el último punto será completamente determinado.

  Tenga en cuenta también que te garantizan que estas intersecciones no desaparecerá cuando su sistema de distancias es consistente.

• A continuación, tiene un conjunto de $n$ $p_k$ $n-1$ dimensiones, pero no sabe si existe alguna menores dimensiones rebanada de ese espacio que se ajusten a los puntos. Por ejemplo, las distancias $d_{jk} = |j-k|$ caben en un uno-dimensional de la rebanada. Su tarea, entonces, es encontrar el menor dimensiones del subespacio que se ajuste a sus puntos.

  La respuesta a esta pregunta se puede encontrar al considerar el conjunto de la separación de los vectores, $\{v_k=p_k-p_1:2\leq k\leq n\}$. La dimensión de la luz es igual al rango de la $(n-1)$-dimensiones de la plaza de la matriz de sus entradas. Es entonces una tarea en el estándar de álgebra lineal para elegir una base a partir de estos vectores, y para expresar el resto en términos de ellos. Que le dará el 'apretado' ajuste posible. Ya sea en tres dimensiones o más, sin embargo, dependerá de su conjunto de distancias.