Der beste Weg, um die minimale Abmessung einer Struktur zu bestimmen, wenn nur Abstände zwischen Punkten gegeben sind

Ich bin auf dieses Problem in einem Bereich der Physik gestoßen, der ziemlich weit von der Informatik entfernt ist, aber es scheint, als wäre die Art von Frage, die in CS untersucht wurde, so dass ich dachte, ich würde mein Glück versuchen, es hier zu stellen.

Stellen Sie sich vor, Sie erhalten eine Menge von Punkten und eine Liste einiger Abstände zwischen den Punkten . Was ist die effizienteste Methode, um die Mindestdimensionalität des Raums zu bestimmen, in den Sie diese Punkte einbetten müssen? Mit anderen Worten, was ist das kleinste so dass es eine Menge von Punkten in die die Abstandsbeschränkungen erfüllen . Ich würde mich auch über eine Antwort für freuen , aber das scheint schwieriger zu sein.$\{v_i\}_{i=1}^n$ k R$d_{ij}$$k$$\mathbb{R}^k$$d_{ij}$$\mathbb{C}^k$

Ich bin glücklich , zu sagen , dass die Abstände müssen übereinstimmen nur innerhalb eines gewissen konstanten Genauigkeit und die Punkte auf Punkte auf einige Gitter von konstanten Abstand beschränkt zu haben, um zu vermeiden , Fragen der mit reellen Zahlen zu berechnen.$d_{ij}$$\epsilon$

In der Tat würde ich mich sehr über eine Lösung für die Entscheidungsversion dieses Problems freuen, bei der mit und gefragt wird, ob eine solche Menge von Eckpunkten existiert oder nicht . Trivialerweise liegt das Problem in NP, da es angesichts einer Menge von Punkten in einfach ist, zu überprüfen, ob sie die Entfernungsanforderungen erfüllen, aber es scheint, dass es für dieses bestimmte Problem subexponentielle Zeitalgorithmen geben sollte.$d_{ij}$$k$$\{v_i\}$$\mathbb{R}^k$

Der naheliegendste Ansatz scheint darin zu bestehen, dimensionale Strukturen iterativ zu erstellen , indem nacheinander zusätzliche Punkte hinzugefügt werden und bei jeder Iteration bestimmt wird, ob eine neue räumliche Dimension hinzugefügt werden muss oder nicht. Das Problem dabei ist, dass Sie anscheinend auf Mehrdeutigkeiten stoßen können, bei denen es mehr als eine Möglichkeit gibt, der vorhandenen Struktur einen Punkt hinzuzufügen, und nicht klar ist, welche zu weniger Dimensionen führt, wenn Sie weitere Punkte hinzufügen.$k$

Lassen Sie mich zum Schluss sagen, dass ich weiß, dass es einfach ist, Entfernungslisten zu erstellen, die in keiner Anzahl von Dimensionen erfüllt werden können (dh solche, die die Dreiecksungleichheit verletzen). In den Fällen, die mir wichtig sind, wird es jedoch immer eine endliche Mindestanzahl von Dimensionen geben, in denen eine zufriedenstellende Menge von Punkten gefunden werden kann.

Dieses Problem wird manchmal als die Vervollständigung einer niederdimensionalen euklidischen Distanzmatrix oder die niederdimensionale euklidische Einbettung eines gewichteten Graphen bezeichnet.

Saxe [Sax79] und Yemini [Yem79] zeigten unabhängig voneinander durch eine einfache Reduktion des Partitionsproblems, dass dieses Problem auch bei einer Dimension NP-vollständig ist; Das heißt, das folgende Problem ist für k = 1 NP-vollständig :

k - dimensionale euklidischer Abstand Matrix Fertigstellung / k -dimentional euklidische Einbettung eines gewichteten Graphen
Instance : eine symmetrische Matrix M „unknown“deren Einträge sind entweder positive ganze Zahlen in binären oder
Frage : Kann die unbekannten Einträge in M so mit reellen Zahlen gefüllt werden? dass M zu einer Distanzmatrix von Punkten im k- dimensionalen euklidischen Raum ℝ ^{k wird} ?
Äquivalent:
Instanz : Ein Graph G, bei dem jede Kante eine positive Ganzzahlgewichtung in Binärform aufweist.
Frage : Können die Eckpunkte von G in diek- dimensionaler euklidischer Raum ℝ ^k, so dass für jede Kante von G der Abstand zwischen den beiden Endpunkten dem Gewicht der Kante entspricht?

Darüber hinaus zeigte Saxe [Sax79] (durch eine umfassendere Reduktion von 3SAT), dass die k- dimensionale euklidische Distanzmatrix-Vervollständigung NP-hart bleibt, auch wenn die Einschränkung besteht, dass alle bekannten Einträge in M für jede positive Ganzzahlkonstante entweder 1 oder 2 sind k . Insbesondere ist das Problem NP-vollständig, auch wenn die bekannten Einträge in M unär sind. [Sax79] enthält auch einige Härteergebnisse zur ungefähren Einbettung.

Übrigens denke ich nicht, dass es trivial ist, dass das Problem in NP liegt; Beachten Sie, dass Sie in einigen Fällen irrationale Koordinaten benötigen, wenn k > 1 ist. Ich weiß nicht, ob es bekannt ist, in NP zu sein.

Verweise

[Sax79] James B. Saxe. Die Einbettbarkeit von gewichteten Graphen in den k- Raum ist stark NP-hart. In Proceedings of the 17. Allerton Conference on Communications, Control, and Computing , S. 480–489, 1979. Ebenfalls in James B. Saxe: Zwei Artikel über Graph Embedding Problems , Department of Computer Science, Carnegie-Mellon University, 1980.

[Yem79] Yechiam Yemini. Einige theoretische Aspekte von Positionsproblemen. Im 20. Jahressymposium über Grundlagen der Informatik (FOCS) , S. 1–8, Okt. 1979. DOI: 10.1109 / SFCS.1979.39

Bei einem festen gibt es eine genaue Charakterisierung von Distanzmatrizen, die Abstände zwischen n Punkten in d- Dimensionen darstellen. Dies stammt aus einem Satz von Schönberg und bezieht sich auf Kerne in ML und negative Distanzen . Diese Charakterisierung kann in polynomialer Zeit getestet werden (dazu werden der Rang berechnet und die negative Bestimmtheit getestet). Ich glaube auch, dass, wenn es eine Einbettung in den euklidischen Raum gibt, diese Einbettung nicht mehr als n Dimensionen hat.$d$$n$$d$$n$