Wiederherstellen einer Punkteinbettung aus einem Diagramm mit Kanten, die nach Punktabstand gewichtet sind

Angenommen, ich gebe Ihnen ein ungerichtetes Diagramm mit gewichteten Kanten und sage Ihnen, dass jeder Knoten einem Punkt im 3D-Raum entspricht. Immer wenn sich zwischen zwei Knoten eine Kante befindet, ist das Gewicht der Kante der Abstand zwischen den Punkten.

Ihr Ziel ist es, die relativen Positionen der Punkte unter Berücksichtigung der verfügbaren Abstände (dargestellt durch die Kantengewichte) zu rekonstruieren. Wenn ich Ihnen zum Beispiel , dann wissen Sie, dass die Punkte die Eckpunkte eines Tetraeders sind . Sie wissen nicht, wo es relativ zum Ursprung oder seiner Ausrichtung ist oder ob es gespiegelt wurde, aber Sie können erkennen, dass es sich um ein Tetraeder handelt.$d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$

Im Allgemeinen ist das Problem einfach, wenn ich Ihnen alle Kantenlängen gebe. Wählen Sie einfach willkürlich einen Punkt , der bei ( 0 , 0 , 0 ) liegt , wählen Sie dann einen benachbarten Punkt p 1 aus und platzieren Sie ihn bei ( d 0 , 1 , 0 , 0 ) . Dann wird ein gemeinsamer Nachbar p 2 trianguliert XY-Ebene, dann wird ein letzter gemeinsamer Nachbar p 3 in den Halbraum z > 0 trianguliert$p_0$$(0,0,0)$$p_1$$(d_{0,1},0,0)$$p_2$$p_3$$z > 0$und bricht die verbleibende Symmetrie (vorausgesetzt, Sie haben keine entarteten Punkte ausgewählt). Mit diesen vier Punkten können Sie alle verbleibenden Punkte triangulieren.

Wenn andererseits einige Kantenlängen fehlen, ist es möglicherweise nicht möglich, die Einbettung wiederherzustellen. Wenn es beispielsweise einen Scheitelpunkt gibt, der das Diagramm beim Schneiden trennt, können die beiden Komponenten, die beim Entfernen getrennt werden, relativ zueinander schwingen.

Was die Fragen aufwirft:

• Wie teuer ist es, eine Lösung zu finden?
• Wie stellen Sie fest, ob eine Lösung bis zur Übersetzung / Rotation / Spiegelung eindeutig ist? Ist 3-Verbundenheit ausreichend? Notwendig?
• Welche Bedingungen machen das Problem trivial?
• Wenn ich nicht verspreche, dass die Kantengewichte tatsächlich dem Punktabstand sin 3d entsprechen, wie teuer ist es dann festzustellen, ob eine Einbettung überhaupt möglich ist?

Ein algorithmischer Ansatz zur Lösung dieses Problems: Behandeln Sie dies als eine Reihe von Knoten, die durch Federn verbunden sind, und lassen Sie sie sich dann in Form setzen / entspannen.

Jede Kante entspricht einer Feder; wenn der Abstand zwischen den Punkten v und w sein soll d v , w , so wird die Feder so gewählt , daß idealerweise er will von Länge sein , d v , w (es länger oder kürzer sein kann, aber diese Kosten Energie). Wir wollen nun nach einer Reihe von Positionen suchen, die die Gesamtenergie minimieren. Angenommen, jeder Scheitelpunkt v befindet sich am Punkt x v ∈ R 3 . Dann wird die Gesamtenergie dieser Anordnung sein$(v,w)$$v$$w$$d_{v,w}$$d_{v,w}$$v$$x_v \in \mathbb{R}^3$

Hier sind die angegeben (sie sind die Gewichte an den Kanten), und wir wollen nach den x v auflösen (sie sind die Koordinaten der Punkte).$d_{v,w}$$x_v$

Wir können nach einer Anordnung suchen, die diese Gesamtenergie minimiert. Diese Anordnung liefert dann einen vernünftigen Kandidaten für die Positionen der Punkte. Dies ist ein Optimierungsproblem, und es gibt Standardtechniken zur Lösung dieser Art von Optimierungsproblemen. Siehe z. B. den Artikel Network Solutions von Erica Klarreich.$x$

Ich glaube nicht, dass es eine Garantie dafür gibt, dass dies die richtige gewünschte Lösung liefert. Es ist möglich, dass sich das Optimierungsproblem auf ein anderes Optimum einstellt, das nicht die tatsächliche Anordnung der gesuchten Punkte widerspiegelt. Wenn Ihr Diagramm jedoch ausreichend dicht ist, kann es vermutlich häufig funktionieren und Ihnen die gewünschte Lösung bieten.

Fußnote: Selbst im besten Fall können wir dieses Problem natürlich nur bis zur Translation, Rotation und Reflexion lösen, da diese Transformationen alle Entfernungen bewahren. Sie können also keine eindeutige Lösung erwarten - aber Sie können hoffen, dass die Lösung bis hin zu Übersetzung, Rotation und Reflexion einzigartig ist.

$\ell_2$$\ell_2$

Das Problem ist NP-Complete . Die Position der Punkte ist ein gutes Zertifikat, also in NP, und Sie können Schaltkreise in "Gibt es eine zufriedenstellende Menge von Punkten?" Codieren. Problem.

Reduzierung von der Schaltungsbewertung zur Entfernungseinbettung

Wir werden die Schaltungsauswertung auf ein Problem der Einbettung von Entfernungen reduzieren, indem wir ein Koordinatensystem erstellen, logische Bits einfügen, Bits gleich verdrahten und Widgets für NOT- und AND-Gatter erstellen.

1. $1$

2. $1$$v$$1$$v$$\frac{1}{\sqrt{3}}$

3. Drähte . Wir können zwei Bits zwingen, gleich zu sein, indem wir sagen, dass der Abstand zwischen ihren Wertpunkten gleich dem Abstand zwischen den Mittelpunkten ihrer Dreiecke ist. Es gibt eine Ausnahme: Wenn die obere oder untere Ecke eines der Bits genau mit der Mittelebene des anderen übereinstimmt. In diesem Fall verwenden wir zuerst einen Draht, um eines der Bits vertikal zu bewegen.

4. $w$$w$$\frac{2}{\sqrt{3}}$$v$$w$$v$

5. IMPLIESIERT . Das äquidistante Problem, das wir mit den Drähten umgehen mussten, ist eigentlich sehr nützlich. Wenn die Bits auf diese Weise ausgerichtet sind, was wir mit einem vertikalen Draht erzwingen können, impliziert der höhere den niedrigeren. Wenn der höhere wahr ist, ist nur die Oberseite des niedrigeren der richtige Abstand. Wenn der höhere Wert falsch ist, befinden sich sowohl der obere als auch der untere Abstand in der richtigen Entfernung.

6. $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_A$$S_B$$\frac{\sqrt 2 + 1}{\sqrt 3}$$S_C$$\frac{\sqrt 2 + 1}{2 \sqrt 3}$$S_A$$S_B$$A$$B$$S_C$$A \neq B$$S_C$$C$$A = B$$S_C$$C$$A$$C$$S_D$$\frac{1}{2 \sqrt 3}$$S_C$$C$$C$$A \neq B$$A=B=C$$A=B$

Mit diesen Elementen können Sie jede Schaltung in eine Entfernungseinbettung codieren. Die Eingänge werden zu Bits, Gates werden in NOTs und ANDs zerlegt, die bei Bedarf neue Bits einführen, und das war's. Erzwingen Sie, dass die Position der Ausgabe wahr ist, und Sie erhalten Ihr Erfüllbarkeitsproblem.

Teilantwort auf Einzigartigkeit : 3-Verbundenheit ist nicht ausreichend.

Beispiel für einen minimalen Zähler: Würfelgraph ($Q_3$

$Q_3$

Nehmen Sie die Ecken des Kartons als die Eckpunkte von Interesse. Jede Ecke eines Kartons hat einen festen Abstand zu anderen Ecken, mit denen er das Gesicht eines Kartons teilt.

$Q_3$

Dies ist als das folgende Problem bekannt und tritt beispielsweise bei der Rekonstruktion von Koordinaten aus Sensornetzwerken auf, die die Entfernung zu nahe gelegenen Knoten messen können. Dieses Dokument kann als Mini-Vermessung zusammen mit führenden Algorithmen dienen. Eine führende Methode ist als Singular Value Projection bekannt, eine weitere Singular Value Threshholding. Die Algorithmen basieren im Allgemeinen auf Matrixalgebra und Rangreduktion. Das Papier implementiert beide Algorithmen und gibt einige empirische Analysen.

Euklidische Entfernungsrekonstruktion aus Teilentfernungsinformationen Xu, Chen