Récupération d'un point d'ancrage à partir d'un graphique avec des bords pondérés par la distance du point

Supposons que je vous donne un graphique non orienté avec des bords pondérés, et que je vous dise que chaque nœud correspond à un point dans l'espace 3D. Chaque fois qu'il y a une arête entre deux nœuds, le poids de l'arête est la distance entre les points.

Votre objectif est de reconstruire les positions relatives des points, étant donné uniquement les distances disponibles (représentées par les poids des bords). Par exemple, si je vous donnais , alors vous savez que les points sont les sommets d'un tétraèdre. Vous ne savez pas où il se trouve par rapport à l'origine, ou son orientation, ou s'il a été mis en miroir, mais vous pouvez dire que c'est un tétraèdre.$d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$

En général, le problème est facile si je vous donne toutes les longueurs de bord. Il suffit de choisir arbitrairement un point pour être à , puis de choisir un point voisin et de le placer à , puis un voisin commun est triangulé sur le XY plan, puis un dernier voisin commun est triangulé dans le demi-espace et brise la symétrie restante (en supposant que vous n'avez pas choisi de points dégénérés). Vous pouvez utiliser ces quatre points pour trianguler tous les autres. ( 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$

En revanche, lorsque certaines longueurs de bord manquent, il peut ne pas être possible de récupérer l'incorporation. Par exemple, s'il existe un sommet qui déconnecte le graphique lors de la découpe, les deux composants qu'il séparerait s'il étaient supprimés peuvent osciller l'un par rapport à l'autre.

Ce qui soulève des questions:

• Combien coûte la recherche d'une solution?
• Comment déterminez-vous si une solution est unique, jusqu'à la traduction / rotation / mise en miroir? La connectivité 3 est-elle suffisante? Nécessaire?
• Quels types de conditions rendent le problème trivial?
• Si je ne promets pas que les poids des bords correspondent réellement à la distance du point sin 3d, combien coûte-t-il pour déterminer si une intégration est possible?

Une approche algorithmique pour résoudre ce problème: traitez-le comme un ensemble de nœuds, reliés par des ressorts, puis laissez-les s'installer / se détendre en forme.

Chaque bord correspond à un ressort; si la distance entre les points et est supposée être , alors le ressort est choisi de sorte qu'il souhaite idéalement être de longueur (il peut être plus ou moins long, mais cela coûte de l'énergie ). Nous voulons maintenant résoudre un ensemble de positions qui minimisent l'énergie totale. Supposons que chaque sommet soit placé au point . Ensuite, l'énergie totale de cet arrangement serav 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$

Ici les sont donnés (ce sont les poids sur les bords), et nous voulons résoudre pour les (ce sont les coordonnées des points). x $d_{v,w}$$x_v$

Nous pouvons résoudre pour un arrangement qui minimise cette énergie totale. Cet arrangement fournit alors un candidat raisonnable pour les positions des points. Il s'agit d'un problème d'optimisation et il existe des techniques standard pour résoudre ce type de problème d'optimisation. Voir, par exemple, l'article Network Solutions d'Erica Klarreich.$x$

Je ne pense pas qu'il y ait de garantie que cela fournira la bonne solution souhaitée. Il est possible que le problème d'optimisation se règle sur un optimum différent qui ne reflète pas la disposition réelle des points que vous recherchez. Cependant, si votre graphique est suffisamment dense, je soupçonne qu'il pourrait souvent fonctionner et vous donner la solution souhaitée.

Note de bas de page: Bien sûr, même dans le meilleur des cas, nous ne pouvons résoudre ce problème que jusqu'à la translation, la rotation et la réflexion, car ces transformations préservent toutes les distances. Ainsi, vous ne pouvez pas vous attendre à une solution unique - mais vous pouvez espérer que la solution est unique jusqu'à la traduction, la rotation et la réflexion.

Enfin, il y a beaucoup de travail sur l'intégration de graphiques dans l' espace , tout en minimisant la distorsion de l'intégration. C'est très lié; vous demandez essentiellement une intégration sans distorsion dans . Ainsi, les techniques développées dans ce contexte pourraient également être utiles pour votre problème. En règle générale, ce travail se concentre sur la recherche d'une incorporation à faible distorsion, car ce travail se concentre sur le cas où il n'y a pas d'intégration parfaite qui fait que toutes les distances correspondent exactement, alors il recherche plutôt une solution à faible distorsion (celle où la plupart des distances aux bords correspondent assez bien) - de sorte que le travail se concentre sur un problème légèrement différent. Cependant, il est possible que leurs techniques soient également efficaces dans votre situation. Ça vaut la peine d'essayer.ℓ $\ell_2$$\ell_2$

Le problème est NP-Complete . La position des points est un bon certificat, donc c'est en NP, et vous pouvez encoder des circuits en "y a-t-il un ensemble satisfaisant de points?" problème.

Réduction de l'évaluation du circuit à l'intégration de la distance

Nous allons réduire l'évaluation des circuits en un problème d'intégration de distance en créant un système de coordonnées, en y mettant des bits logiques, en câblant les bits de manière égale et en créant des widgets pour les portes NOT et AND.

1. Coordonnées . Nous avons besoin d'une sorte de système de coordonnées avec lequel nous pouvons positionner des points. Pour ce faire, créez un tétraèdre "de base" de points. Ajoutez quatre points, tous déclarés éloignés de . Cela force la forme de ces quatre points en un tétraèdre. Nous pouvons positionner d'autres points par rapport à notre système de coordonnées tétraèdre en spécifiant leur distance à chacun des quatre coins de la base. Le tétraèdre peut être translaté, tourné et réfléchi, mais la même chose se produira également pour tous les autres points.$1$

2. Des bits . Pour faire un peu, on positionne un triangle de points par rapport au tétraèdre de base. La normale du triangle doit pointer vers le haut le long de l'axe Z, de sorte que le triangle soit parallèle au plan XY (en coordonnées tétraèdre). De plus, ses bords doivent avoir une longueur de . Cela fait, nous ajoutons un point "valeur" , spécifié à une distance de des trois autres. Nous ne connectons pas au système de coordonnées de base. Cela lui donne deux positions possibles: centré au-dessus ou au-dessous du triangle, comme coin final d'un tétraèdre. Le bit est activé si le point est au-dessus du triangle et désactivé s'il est inférieur.contre 1 contre $1$$v$$1$$v$$\frac{1}{\sqrt{3}}$

3. Fils . Nous pouvons forcer deux bits à être égaux en disant que la distance entre leurs points de valeur est égale à la distance entre les centres de leurs triangles. Il existe une exception: lorsque le coin supérieur ou inférieur de l'un des bits est exactement aligné avec le plan central de l'autre. Dans ce cas, nous utilisons d'abord un fil pour déplacer l'un des bits verticalement.

4. NON . Nous pouvons obtenir la négation d'un bit en ajoutant un deuxième point de valeur au même triangle, mais en exigeant que soit à une distance de de . Cela oblige à prendre la position opposée à , par rapport au triangle, nous donnant un peu la valeur opposée.w $w$$w$ vw$\frac{2}{\sqrt{3}}$$v$$w$$v$

5. IMPLIES . Le problème équidistant que nous avons dû contourner avec les fils est en fait très utile. Lorsque les bits s'alignent de cette manière, que nous pouvons forcer avec un fil vertical, le plus élevé implique le plus bas. Si le plus haut est vrai, seul le haut du plus bas est à la bonne distance. Si le plus haut est faux, le haut et le bas sont à la bonne distance.

6. ET . Pour qu'un bit soit égal à ET , nous avons besoin de deux implications et d'un widget pour forcer l'égalité lorsque et sont d'accord. Les implications sont que et . Pour créer le widget, nous déplaçons et verticalement afin qu'ils soient au même niveau et à une distance , puis nous déplaçons pour être équidistants entre eux. On ajoute ensuite un point et une distance de etA B A B $C$$A$$B$$A$$B$$C \implies A$A B $C \implies B$$A$$B$ CSASB$\frac{2}{\sqrt 3}$$C$$S_A$$S_B$ ABSASB$\frac{\sqrt 2 - 1}{2 \sqrt 3}$$A$$B$respectivement, et force la distance entre et à être . Nous ajoutons également un point une distance de et . Cela crée une chaîne entre les points de valeur et , avec au centre de la chaîne. Lorsque , la chaîne est tendue jusqu'à la limite et est au centre du triangle deLorsque les maillons des chaînes sont obligés d'aller dans des directions opposées exactes, en poussant$S_A$$S_B$ SC$\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$à la limite et à placer sur point de valeur d » égal à . Pour forcer le point de valeur de , nous insérons un point une distance à la fois de et du point de valeur deCela ne contraignent point de valeur de quand , mais les forces quand .$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$

Avec ces éléments, vous pouvez encoder n'importe quel circuit dans une intégration à distance. Les entrées deviennent des bits, les portes se décomposent en NOTs et ANDs introduisant de nouveaux bits si nécessaire, et c'est tout. Forcez la position de la sortie à être vraie et vous obtenez votre problème de satisfiabilité.

Réponse partielle sur l' unicité : la connectivité 3 n'est pas suffisante.

Exemple de compteur minimal: graphe cubique ( de la famille Hypercube Graph )$Q_3$

Pour voir comment la fixation de la longueur de tous les bords dans ne donne pas de position aux sommets dans un espace 3D unique jusqu'à la translation / rotation / mise en miroir, regardez comment vous pouvez aplatir une boîte en carton (avec 2 faces opposées supprimées) .$Q_3$

Prenez les coins de la boîte en carton pour être les sommets d'intérêt. Chaque coin d'une boîte en carton a une distance fixe par rapport aux autres coins avec lesquels il partage le visage d'une boîte.

Bien que le graphique résultant ait encore plus d'arêtes que , il permet toujours d'aplatir la boîte en carton --- une transformation qui ne peut pas être produite par translation / rotation / mise en miroir.$Q_3$

ceci est connu comme le problème suivant et se produit par exemple avec la reconstruction de coordonnées à partir de réseaux de capteurs qui peuvent mesurer la distance aux nœuds voisins, et ce document peut servir de mini-enquête avec des algorithmes principaux. une méthode de pointe est connue sous le nom de projection de valeur singulière, un autre seuil de valeur singulière. les algorithmes sont généralement basés sur l'algèbre matricielle et la réduction du rang. l'article met en œuvre les deux algorithmes et donne une analyse empirique.

Reconstruction de la distance euclidienne à partir d'informations partielles sur la distance Xu, Chen