Erkennen der Koplanarität durch gegebene paarweise Abstände

7

Betrachten Sie einen ungerichteten gewichteten Graphen , wobei so ist, dass die Punkte 3D sind und das Gewicht einer Kante dem (euklidischen) Abstand zwischen ihren Endpunkten entspricht. Beachten Sie, dass wir nicht die Koordinaten der Punkte in V erhalten. Wir erhalten möglicherweise nicht alle paarweisen Abstände, sodass der Graph nicht vollständig sein muss und möglicherweise sogar spärlich ist.G=(V.,E.)V.R.3

Angenommen, wir erhalten und erfahren, dass es Ebenen gibt, sodass alle Eckpunkte zu mindestens einer dieser Ebenen gehören. Wir wollen solche Flugzeuge mit einer zusätzlichen Einschränkung finden:kkk

Um zu bestimmen, ob 4 Punkte nur aufgrund ihrer paarweisen Abstände koplanar sind, ist die einfachste Methode die Verwendung der Cayley-Menger-Determinante . Für unser Problem würde dies erfordern, dass der Graph ziemlich dicht ist, da wir die meisten paarweisen Abstände kennen müssten, um Cayley-Menger anzuwenden. Die Einschränkung besteht darin, Ebenen ohne Verwendung der Cayley-Menger-Determinante zu finden.k

Wenn dies unmöglich ist, können wir einen Beweis erhalten, der besagt, dass dies unmöglich ist? Mit anderen Worten, können wir beweisen, dass wir für einen solchen Graphen und gegebenes , wenn wir genug Informationen haben, um Ebenen für auf irgendeine Weise zu finden, genug Informationen haben, um Cayley-Menger zu verwenden, um Ebenen zu finden ?GkkGk

Padawan
quelle
Ein Hinweis, dass die Cayley-Menger-Determinante für diesen Zweck ausreicht, wäre hilfreich, wenn Sie eine kennen. Was meinst du mit "alle paarweisen Abstände zwischen jeweils 4 Knoten"? Gibt es nicht so viele paarweise Abstände wie Kanten mit Punkten als Eckpunkte in einem Diagramm? Ist der Algorithmus, an den Sie denken, die Koplanarität aller 4-Punkte-Entscheidungen? mehr auf coplanar
vzn
Idee: denke, das verallgemeinert. Lege alle Punkte in eine Matrix und finde ihren Rang. Wenn es 2 ist, sind sie alle koplanar. das könnte in der Mathematik besser rübergehen ...?
vzn
@vzn Das ist eine gute Idee, aber was ist, wenn es mehr als eine koplanare Sensorgruppe gibt?
Padawan
Es ist nicht klar, was Sie fragen. Bekommen wir die Punkte oder nicht? Was meinst du genau mit "gegebener Menge von Punkten und paarweisen Abständen (nicht die Koordinaten)"? Gib ein Beispiel.
Craig Gidney
1
Im Allgemeinen ist die kFlugzeuge sind möglicherweise nicht eindeutig. Zum Beispiel, wenn die Eckpunkte Eckpunkte eines Würfels sind undk=2Dann funktionieren die obere und untere Ebene ebenso wie die Vorder- und Rückseite sowie die linke und rechte. Du hast über das gesprochen kFlugzeuge, aber vermutlich sind Sie in Ordnung mit der Suche nach irgend k Flugzeuge, die immer noch den Trick machen, alle Punkte in abzudecken V?
Amit Kumar Gupta

Antworten:

3

Ich denke, wenn das Eingabediagramm 3-fach verbunden ist und Sie einen beliebigen Ursprung und eine beliebige Ausrichtung annehmen, können Sie die ursprünglichen Punkte neu erstellen. Besonders wenn Sie K_4 finden, um den Triangulationsprozess zu starten.

Sobald wir die Punkte haben, werden gierige Strategien verfügbar. Sie sind vielleicht nicht optimal, aber vielleicht reichen sie für Ihre Zwecke.

Ich habe gefragt, ob die Einbettung als separate Frage wiederhergestellt werden soll.

Zufällige Gier

Bis wir weniger als drei nicht disqualifizierte Punkte haben, wählen Sie willkürlich drei davon aus, geben Sie die Ebene ab, die durch sie verläuft, und markieren Sie alle Punkte auf der Ebene als disqualifiziert.

Nehmen Sie die verbleibenden nicht disqualifizierten Punkte (falls vorhanden), kombinieren Sie sie mit willkürlichen disqualifizierten Punkten und geben Sie das Flugzeug ab, das durch sie hindurchgeht.

Die Flugzeuge, die wir abgaben, deckten alle Punkte ab. Die Anzahl der Flugzeuge, die wir abgegeben haben, ist höchstensn3und jeder erfordert das Scannen der verbleibenden Punkte, so dass dieser Algorithmus benötigt O(n2) Zeit (schneller als die Berechnung einer Determinante).

Wenn die Anzahl der Flugzeuge knDann haben wir ziemlich gute Chancen, eines der großen Flugzeuge zu treffen. Ich bin mir nicht sicher, wie hoch die erwartete Laufzeit ist, aber ich würde es mir vorstellenO(nk3logk). (Das basiert auf dem Coupon-Sammler-Problem, das impliziert, dass wir es brauchenklogk Treffer zu sammeln k Flugzeuge, und dass die Chancen eines Treffers sind (1/k)2 Die erwartete Zeit zwischen den Treffern ist also k2).

Priorisierte Gier

Eine andere Sache, die wir tun können, wenn wir nach den Punkten suchen können, ist, alle Drillinge zu durchlaufen und zu zählen, wie viele Punkte sich auf dieser Ebene befinden. Dann ergeben wir wiederholt die Ebene, die die meisten Punkte abdeckt, bis keine Punkte mehr übrig sind.

Wenn wir bei der Auswahl der nächsten Ebene keine disqualifizierten Punkte berücksichtigen, ist dies erforderlich O(n3logt) Zeit wo tist die Anzahl der Flugzeuge, die wir zurückgeben. Wenn wir Prioritäten neu setzen, kann dies meiner Meinung nach immer noch in getan werdenO(n3logt) (Die Anzahl der disqualifizierten Punkte in anderen Flugzeugen kann sich nur um 2 ändern, sodass es möglicherweise möglich ist, das Gleichgewicht auf clevere Weise auszugleichen.)

Dieser Ansatz sollte besser funktionieren, aber ich glaube auch nicht, dass dies garantiert ist t=k. Wir können die Punkte wahrscheinlich so anordnen, dass wir mit dem Flugzeug, das die meisten von ihnen abdeckt, den falschen Weg einschlagen.

Craig Gidney
quelle
Ihr allererster Satz des ersten Algorithmus lautet im Grunde: "Wähle 3 Punkte und disqualifiziere alle Punkte, die mit diesen 3 koplanar sind." Aber wie bestimmen Sie, welche Punkte koplanar sind? Das ist der springende Punkt dieser Frage. Angenommen, Sie kennen die Koordinaten der Punkte nicht und kennen nur einige ihrer paarweisen Abstände. Wie erkennen Sie die Koplanarität?
Amit Kumar Gupta
@AmitKumar Jedes beliebige Triplett von Punkten ist koplanar, weil sie eine Ebene definieren . Ein Eckfall ist, wenn sie entartet sind (zwei der Punkte sind gleich oder die drei Punkte fallen auf eine Linie). In diesem Fall sind sie immer noch koplanar, aber viele Ebenen können sie abdecken.
Craig Gidney
@AmitKumar Oh, ich sehe, dass Sie gemeint haben, wie Sie testen, ob sich ein Punkt in einem Flugzeug befindet. Grundsätzlich ist das Punktprodukt die Normalen der Ebene gegen das Delta des Punktes zu einem Punkt in der Ebene . Wenn das Punktprodukt Null ist (oder nahe Null, wenn Sie sich annähern), liegt der Punkt auf der Ebene. Sie tun dies für jeden nicht disqualifizierten Punkt.
Craig Gidney
@AmitKumarGupta Genauer gesagt geht es nicht darum, herauszufinden , welche Punkte sich auf einer Ebene befinden. Es geht darum, wie Sie einen kleinen Satz von Ebenen auswählen, die die Punkte abdecken, mit der zusätzlichen Falte, dass Sie nur einige der Zwischenpunktabstände anstelle der Punkte selbst erhalten.
Craig Gidney
1
@AmitKumarGupta Wenn Sie einen K_4 haben, setzen Sie einen von ihnen auf (0,0,0), einen anderen auf (x, 0,0), den nächsten auf (y, z, 0) und den letzten auf (a, b, c) mit c> 0. Wenn Sie nicht nach einer eindeutigen Einbettung bis hin zu Übersetzung / Rotation / Spiegelung suchen können, gibt es meiner Meinung nach keine genau definierte Lösung. Sie würden Dinge wie starre Gruppen von Punkten erhalten, die durch einen Hebel verbunden sind, um den Sie sich drehen können, ohne die Abstandsbeschränkungen zu verletzen, und ich glaube nicht, dass die Flugzeuge diesen Informationsverlust überleben können.
Craig Gidney
3

RANSAC wäre eine mögliche Methode, um Ebenen zu finden, die einen großen Teil der Punkte abdecken.

Angenommen, ein großer Teil der Punkte verläuft durch eine Ebene P, sagen, n/10von ihnen. So können wir es finden:

Wählen wir also zufällig 4 Punkte aus dem n;; Nennen Sie diese Punkteq,r,s,t. Angenommen, wir kennen die Abstände zwischen all diesen Paaren (sie bilden eine 4-Clique,K4). Dann können wir die Cayley-Menger-Determinante verwenden, um zu sehen, ob sie koplanar sind. Angenommen, sie sind koplanar. Dann könnten wir versuchen, uns gegenseitig zu testenx und zu sehen, ob wir erkennen können, ob es mit der von gebildeten Ebene koplanar ist q,r,s,t. Wir können dies möglicherweise nur testen, wenn der zusätzliche Punktubildet zusammen mit einigen anderen Punkten, von denen bekannt ist, dass sie sich in der Ebene befinden, eine 4-Clique. Am Ende, wenn wir eine signifikante Anzahl von Punkten gefunden haben, die auf der Ebene liegen, die durch gebildet wirdq,r,s,tWir behalten dieses Flugzeug. Machen Sie dies beispielsweise für 1000 zufällige Auswahlmöglichkeiten vonq,r,s,t.

Wie gut wird das funktionieren? Nehmen wir an, wir modellieren den Graphen als zufälligen Graphen, bei dem jede mögliche Kante mit Wahrscheinlichkeit erscheintp (so erwarten wir pn(n1)/2Kanten im Durchschnitt). Dann ist die Wahrscheinlichkeit, dass eine zufällig ausgewählte Menge von 4 Punkten eine 4-Clique im Diagramm bildetp6. Daher, wenn wir zumindest probieren104/p6 Auswahl von q,r,s,tWir erwarten, mindestens eine zu finden, bei der sie das Flugzeug enthüllen P.. Auch die Wahrscheinlichkeit, dass ein zusätzlicher Punktu bildet eine 4-Clique mit mindestens drei von p,q,r ist p3Wenn wir also vier Punkte finden q,r,s,t im Flugzeug Perwarten wir zumindest zu finden p3n/10 der Punkte in der Ebene P. (Eigentlich werden wir wahrscheinlich noch viel mehr finden. Sobald wir diese habenp3n/10 Punkte, jetzt die Wahrscheinlichkeit, dass ein zusätzlicher Punkt v bildet eine 4-Clique mit mindestens drei davon 1(1p3)p3n/101exp{p6n/10}, die deutlich größer ist als p3.) Mit anderen Worten, sobald wir Punkte gefunden haben q,r,s,t im Flugzeug PEs ist wahrscheinlich, dass wir dieses Flugzeug behalten werden.

Solange Sie genügend 4-Punkt-Kombinationen abtasten und Ihr Diagramm dicht genug ist, erkennt dieses Verfahren wahrscheinlich alle Ebenen, die einen großen Teil der Punkte abdecken.

DW
quelle
Wir müssen jedoch erneut die Cayley-Menger-Determinante für jeden zusätzlichen Punkt verwenden, den wir testen.
Padawan
@cagirici, ja, das machen wir. Meine Antwort steht im Einklang mit der Problemstellung und dem in der Frage angegebenen Detaillierungsgrad. Wenn es einen Grund gibt, warum Ihre spezielle Einstellung nicht berücksichtigt wird, können Sie Ihre Frage bearbeiten, um spezifischere technische Anforderungen bereitzustellen. ("Cayley-Menger nicht verwenden" ist keine gültige technische Anforderung. "Muss an Diagrammen arbeiten, die sehr spärlich sind" ist eine Anforderung, wenn Sie formulieren können, was Sie unter "sehr spärlich" verstehen. Eine Anforderung gibt an, was Sie möchten zu erreichen, nicht wie.)
DW
Nach einer langen Zeit bin ich wieder bei diesem Problem :) Wenn ich sage "Der Algorithmus sollte mit inkonsistenten Entfernungsmessungen funktionieren", ist dies eine Voraussetzung? Wenn ja, funktioniert dieser Algorithmus mit fehlerhaften Entfernungsmessungen?
Padawan
3

Leider ist die Antwort, dass dies ein NP-Complete-Problem ist. Mit nur 4 Punktebenen können Sie Erfüllbarkeitsprobleme dahingehend codieren, ob es einen Punktsatz gibt, der einen spärlichen Satz von Abständen erzeugt oder nicht.

Das heißt, Sie können Probleme erstellen, bei denen festgestellt werden muss, ob eine fünfte Ebene erforderlich ist oder nicht, um 3-SAT-Probleme zu lösen. Sie können zwei solcher Probleme kombinieren, wobei genau eines die fünfte Ebene erfordert, um die Anzahl der Ebenen konstant zu halten und den Algorithmus zu zwingen, 3-SAT-Probleme zu lösen, selbst wenn er es weißk vor der Zeit.

Das Problem hat also keine Polynomzeitlösung im ungünstigsten Fall, es sei denn, P = NP.

Craig Gidney
quelle
-1

Ich versuche eine Antwort, obwohl die Frage möglicherweise etwas unklar ist. Die Hälfte davon besagt, dass die Punkte angegeben sind, die andere Hälfte, dass paarweise Abstände angegeben sind. Ich gehe davon aus, dass für diese Antwort Punktkoordinaten angegeben sind. Es besteht eine enge Verbindung zwischen der Berechnung der Determinante und dem Matrixrang. Es gibt eine Verallgemeinerung wie folgt. Erstellen Sie die Matrix aus 3D-Vektoren. Diese können entweder Spalten- oder Zeilenvektoren sein. Berechnen Sie den Rang . Wenn es 2 ist, sind die Punkte koplanar. Die paarweisen Abstände können aus den Koordinaten berechnet werden und sind zur Berechnung / Bestimmung des Matrixrangs nicht erforderlich.

vzn
quelle
1
Könnten Sie bitte den Satz kopieren und einfügen, der besagt, dass die Koordinaten der Punkte angegeben sind? Die Frage besagt, dass ein Punktesatz gegeben ist. Nicht die Koordinaten.
Padawan
nehme "Punktmenge = Koordinaten". Sie sagen, Punkte sind in Kommentaren nicht vollständig, aber nicht in der Frage. Wie definiert man "Punktmengen" ohne Koordinaten? Möglicherweise muss dies abgestimmt werden, um zu schließen, wenn es in der aktuellen Form ohne Überarbeitung inkonsistent oder unbeantwortbar ist. Ich versuche, etwas Verantwortliches zu extrahieren. Die Kommentare und Fragen stimmen nicht überein. Die Antwort bestimmt, ob alle Punkte koplanar sind. Vielleicht möchten Sie nur wissen, ob Teilmengen aller Punkte bei einigen paarweisen Abständen koplanar sind?
vzn