Recuperación de un punto incrustado de un gráfico con bordes ponderados por la distancia del punto

Supongamos que le doy un gráfico no dirigido con bordes ponderados y le digo que cada nodo corresponde a un punto en el espacio 3d. Siempre que haya un borde entre dos nodos, el peso del borde es la distancia entre los puntos.

Su objetivo es reconstruir las posiciones relativas de los puntos, dadas solo las distancias disponibles (representadas por los pesos de los bordes). Por ejemplo, si te di , entonces sabes que los puntos son los vértices de un tetraedro. No sabes dónde está en relación con el origen, o su orientación, o si se ha reflejado, pero puedes decir que es un tetraedro.$d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$

En general, el problema es fácil si le doy todas las longitudes de borde. Simplemente elija arbitrariamente un punto para que esté en , luego elija un punto vecino y colóquelo en , luego un vecino común se triangula en el XY plano, luego un vecino común final se triangula en el medio espacio y rompe la simetría restante (suponiendo que no haya elegido puntos degenerados). Puedes usar esos cuatro puntos para triangular todos los restantes. ( 0 , 0 , 0 ) p 1 ( d 0 , 1 , 0 , 0 ) p 2 p 3 z > $p_0$$(0,0,0)$$p_1$$(d_{0,1},0,0)$$p_2$$p_3$$z > 0$

Por otro lado, cuando faltan algunas longitudes de borde, puede que no sea posible recuperar la incrustación. Por ejemplo, si hay un vértice que desconecta el gráfico cuando se corta, entonces los dos componentes que separaría si se quitan pueden oscilar uno con respecto al otro.

Lo que plantea las preguntas:

• ¿Qué tan costoso es encontrar una solución?
• ¿Cómo se determina si una solución es única, hasta la traducción / rotación / duplicación? ¿Es suficiente la 3-conectividad? ¿Necesario?
• ¿Qué tipo de condiciones hacen que el problema sea trivial?
• Si no prometo que los pesos de los bordes realmente corresponden a la distancia de punto en 3d, ¿qué tan costoso es determinar si es posible una incrustación?

Un enfoque algorítmico para resolver este problema: trate esto como un conjunto de nodos, conectados por resortes, luego déjelos asentarse / relajarse en forma.

Cada borde corresponde a un resorte; si se supone que la distancia entre los puntos y es , entonces se elige el resorte, por lo que idealmente debe tener una longitud (puede ser más largo o más corto, pero esto cuesta energía ) Ahora queremos resolver un conjunto de posiciones que minimicen la energía total. Supongamos que cada vértice se coloca en el punto . Entonces la energía total de este arreglo seráv w d v , w d v , w v x v ∈ R$(v,w)$$v$$w$$d_{v,w}$$d_{v,w}$$v$$x_v \in \mathbb{R}^3$

Aquí se dan los (son los pesos en los bordes), y queremos resolver los (son las coordenadas de los puntos). x $d_{v,w}$$x_v$

Podemos resolver un arreglo que minimiza esta energía total. Este arreglo proporciona un candidato razonable para las posiciones de los puntos. Este es un problema de optimización, y existen técnicas estándar para resolver este tipo de problema de optimización. Ver, por ejemplo, el artículo Network Solutions de Erica Klarreich.$x$

No creo que haya ninguna garantía de que esto proporcionará la solución deseada correcta. Es posible que el problema de optimización se establezca en un óptimo diferente que no refleje la disposición real de los puntos que estaba buscando. Sin embargo, si su gráfico es lo suficientemente denso, sospecho que a menudo podría funcionar y le dará la solución deseada.

Nota al pie: Por supuesto, incluso en el mejor de los casos, solo podemos resolver este problema hasta la traslación, rotación y reflexión, ya que esas transformaciones preservan todas las distancias. Por lo tanto, no puede esperar una solución única, pero puede esperar que la solución sea única hasta la traslación, rotación y reflexión.

Finalmente, hay mucho trabajo en incrustar gráficos en espacio, mientras se minimiza la distorsión de la incrustación. Eso está muy relacionado; básicamente está pidiendo una incrustación de distorsión cero en . Por lo tanto, las técnicas desarrolladas en ese contexto también podrían ser útiles para su problema. Típicamente, ese trabajo se enfoca en encontrar una incrustación de baja distorsión, porque ese trabajo se enfoca en el caso donde no hay una incrustación perfecta que haga que todas las distancias coincidan exactamente, por lo que busca una solución de baja distorsión (una donde la mayoría de las distancias al borde coinciden bastante bien), por lo que el trabajo se centra en un problema ligeramente diferente. Sin embargo, es posible que sus técnicas también sean efectivas en su situación. Vale la pena intentarlo.ℓ $\ell_2$$\ell_2$

El problema es NP-Complete . La posición de los puntos es un buen certificado, por lo que está en NP y puede codificar circuitos en "¿hay un conjunto de puntos satisfactorio?" problema.

Reducción de la evaluación del circuito a la inclusión a distancia

Vamos a reducir la evaluación del circuito en un problema de integración de distancia creando un sistema de coordenadas, colocando bits lógicos en él, conectando los bits para que sean iguales y creando widgets para las puertas NOT y AND.

1. Coordenadas . Necesitamos algún tipo de sistema de coordenadas con el que podamos posicionar puntos. Haga esto creando un tetraedro de puntos "base". Agregue cuatro puntos, todos declarados a una distancia de entre sí. Esto fuerza la forma de esos cuatro puntos en un tetraedro. Podemos posicionar otros puntos en relación con nuestro sistema de coordenadas de tetraedro especificando su distancia a cada una de las cuatro esquinas de la base. El tetraedro se puede traducir, rotar y reflejar, pero lo mismo sucederá con todos los demás puntos también.$1$

2. Los bits . Para hacer un poco, colocamos un triángulo de puntos en relación con el tetraedro base. La normal del triángulo debe apuntar hacia arriba a lo largo del eje Z, de modo que el triángulo sea paralelo al plano XY (en coordenadas de tetraedro). También sus bordes deben tener longitud . Una vez hecho esto, agregamos un "valor" punto , especificado para ser una distancia de de los otros tres. Nosotros no conectamos a la base del sistema de coordenadas. Esto le da dos posiciones posibles: centrado arriba o debajo del triángulo, como la esquina final de un tetraedro. El bit está activado si el punto está por encima del triángulo, y desactivado si está por debajo.v 1 v $1$$v$$1$$v$$\frac{1}{\sqrt{3}}$

3. Cables . Podemos forzar que dos bits sean iguales diciendo que la distancia entre sus puntos de valor es igual a la distancia entre los centros de sus triángulos. Hay una excepción: cuando la esquina superior o inferior de uno de los bits se alinea exactamente con el plano central del otro. En ese caso, primero usamos un cable para mover uno de los bits verticalmente.

4. NO . Podemos obtener la negación de un bit agregando un segundo punto de valor al mismo triángulo, pero requiriendo que sea ​​una distancia de de . Esto obliga a a tomar la posición opuesta a , con respecto al triángulo, dándonos un poco con el valor opuesto.$w$$w$$\frac{2}{\sqrt{3}}$$v$$w$$v$

5. IMPLICA . El problema equidistante que tuvimos que solucionar con los cables es realmente bastante útil. Cuando los bits se alinean de esa manera, que podemos forzar con un cable vertical, el más alto implica el más bajo. Si el más alto es verdadero, solo la parte superior del más bajo está a la distancia correcta. Si el más alto es falso, tanto la parte superior como la inferior están a la distancia correcta.

6. Y . Para hacer que un bit sea ​​igual a y , necesitamos dos implicaciones y un widget para forzar la igualdad cuando y están de acuerdo. Las implicaciones son sólo y . Para hacer el widget, movemos y verticalmente para que estén en el mismo nivel y a una distancia aparte, luego movemos para ser equidistantes entre ellos. Luego agregamos puntos y una distancia de y$C$$A$$B$$A$$B$$C \implies A$$C \implies B$$A$$B$$\frac{2}{\sqrt 3}$$C$$S_A$$S_B$$\frac{\sqrt 2 - 1}{2 \sqrt 3}$$A$$B$'s puntos de valor respectivamente, y fuerzan la distancia entre y para ser . También agregamos un punto una distancia de y . Esto crea una cadena entre los puntos de valor de y , con en el centro de la cadena. Cuando , la cadena se estira hasta el límite y está en el centro del triángulo deCuando los eslabones de las cadenas se ven obligados a ir en direcciones exactamente opuestas, empujando$S_A$$S_B$$\frac{\sqrt 2 + 1}{\sqrt 3}$$S_C$ SASBABSCA≠BSCCA=BSCCACSD$\frac{\sqrt 2 + 1}{2 \sqrt 3}$$S_A$$S_B$$A$$B$$S_C$$A \neq B$$S_C$$C$$A = B$al límite y colocando en punto de valor 's igual por . Para forzar el punto de valor de , insertamos un punto una distancia del punto de valor de y deEsto no limita punto de valor 's cuando , pero las fuerzas de cuando .$S_C$$C$$A$$C$$S_D$ SCCCA≠BA=B=CA=$\frac{1}{2 \sqrt 3}$$S_C$$C$$C$$A \neq B$$A=B=C$$A=B$

Con esos elementos, puede codificar cualquier circuito en una incrustación de distancia. Las entradas se convierten en bits, las puertas se descomponen en NOT y AND que introducen nuevos bits según sea necesario, y eso es todo. Fuerce la posición de la salida para que sea verdadera y obtendrá su problema de satisfacción.

Respuesta parcial sobre la unicidad : la 3-conectividad no es suficiente.

Ejemplo de contador mínimo: gráfico de cubo ( de la familia de gráficos Hypercube )$Q_3$

Para ver cómo arreglar la longitud de todos los bordes en no da posiciones a los vértices en un espacio que es único hasta la traslación / rotación / reflejo, observe cómo puede aplanar una caja de cartón (con 2 caras opuestas eliminadas) .$Q_3$

Tome las esquinas de la caja de cartón como vértices de interés. Cada esquina de una caja de cartón tiene una distancia fija de otras esquinas con las que comparte la cara de una caja.

Si bien el gráfico resultante tiene incluso más aristas que , todavía permite que la caja de cartón se , una transformación que no puede producirse por traslación / rotación / reflejo.$Q_3$

Esto se conoce como el siguiente problema y ocurre, por ejemplo, con la reconstrucción de coordenadas a partir de redes de sensores que pueden medir la distancia a los nodos cercanos, y este documento puede servir como una mini encuesta junto con los algoritmos principales. un método líder se conoce como Proyección de valor singular, otro umbral de valor singular. los algoritmos generalmente se basan en álgebra matricial y reducción de rango. El documento implementa ambos algoritmos y ofrece algunos análisis empíricos.

Reconstrucción de distancia euclidiana a partir de información de distancia parcial Xu, Chen