Berechnen Sie bei zwei Mengen und jeweils disjunkte Punkte in der Ebene enthalten, den kürzesten Abstand zwischen einem Punkt in und einem Punkt in , dh .
Ich bin nicht sicher, ob ich Recht habe, aber dieses Problem ist sehr ähnlich zu Problemen, die durch lineare Programmierung in der Computergeometrie gelöst werden können. Die Reduktion auf LP ist jedoch nicht einfach. Mein Problem hängt auch damit zusammen, den dünnsten Punkt zwischen zwei Punktmengen zu finden, der offensichtlich durch LP in im zweidimensionalen Raum gelöst werden kann.
Antworten:
Ich habe eine Lösung, die etwas kompliziert erscheint, aber effizienter sein sollte als die naive Brute-Force-Suche:O(n2)
Der Rest ist in Pseudocode, um es klarer zu machen:
Das heißt, indem Sie die Punkte entlang vorsortieren , können Sie Paare herausfiltern, die niemals innerhalb von voneinander liegen, da entlang immer.v d bk−aj v ≤∥bk−aj∥
Im schlimmsten Fall ist dies immer noch , aber wenn und gut getrennt sind, sollte es viel schneller sein, aber nicht besser als , was erforderlich ist für die Sortierung.O(n2) A B O(nlogn)
Aktualisieren
Diese Lösung wird keineswegs aus dem Hut gezogen. Es ist ein Sonderfall dessen, was ich in Partikelsimulationen verwende, um alle interagierenden Partikelpaare mit räumlicher Gruppierung zu finden. Meine eigene Arbeit, die das allgemeinere Problem erklärt, ist hier .
Was den Vorschlag betrifft, einen modifizierten Line-Sweep-Algorithmus zu verwenden, bin ich, obwohl intuitiv einfach, nicht davon überzeugt, dass dies in wenn disjunkte Mengen berücksichtigt werden. Gleiches gilt für Rabins randomisierten Algorithmus.O(nlogn)
Es scheint nicht viel Literatur mit dem nächsten Paar Problem in disjunkte Mengen zu tun zu sein, aber ich habe festgestellt , das , was ist unter keinen Anspruch macht , und das , was nicht scheint Ansprüche über irgendetwas zu erheben.O(n2)
Der obige Algorithmus kann als eine Variante des in der ersten Veröffentlichung vorgeschlagenen Ebenen-Sweeps angesehen werden (Shan, Zhang und Salzberg). Anstatt jedoch die Achse und keine Sortierung zu verwenden, wird die Achse zwischen den Sätzen verwendet und die Sätze werden durchlaufen in absteigender / aufsteigender Reihenfolge.x
quelle
Sie können den Linienweep-Algorithmus "nächstes Paar" anpassen, der .O(nlogn)
Die einzige Änderung, die Sie vornehmen müssen, besteht darin, Paare zu ignorieren, die zu derselben Gruppe gehören.
Bearbeiten: Dies ist eigentlich nicht einfach (oder sogar möglich), wie ich beschrieben habe. Siehe Kommentare zur Diskussion.
quelle
Bei solchen Problemen besteht die Idee darin, aus einer der Mengen eine geordnete Struktur zu erstellen, die effiziente Abfragen des nächsten Nachbarn ermöglicht. Das klassische Papier, das eine O (log n) -Abfragestruktur für eine beliebige Dimension vorstellte, war:
Shamos und Hoey über Voronoi-Lösungen
Seitdem wurde eine Reihe anderer Raumpartitionen erstellt, die auf Ideen von Delauney-Tesselationen basieren und sich auch in einer Vielzahl von Subraum-Sweep-Beschreibungen niederschlagen. Es ist zu beachten, dass die Voronoi-Methode aufgrund ihrer ebenen Partitionierung, die den Konstruktionsschritt O (n log n) macht, auch unter eine allgemeine Divide-and-Conquer-Beschreibung fallen würde.
Die grundlegende Lösung für dieses Problem lautet also:
Wie man an der Komplexität jedes Schritts sehen kann, ist die Gesamtkomplexität O (n log n). Für den modernen Leser, der sich nicht mit klassischen Artikeln befasst, wird dies in vielen Algorithmusbüchern behandelt, z. B. "The Algorithm Design Manual" von Skiena.
quelle
Die Untergrenze für dieses Problem ist unter dem algebraischen Entscheidungsbaummodell. Ich werde hier eine grobe Skizze des Beweises geben.O(n∗logn)
Wir werden die Instanz des Elementunterscheidungsproblems E auf C reduzieren.
Wir wissen, dass die Untergrenze der Laufzeit für die Entscheidung über das Problem der Elementunterscheidbarkeit . Daher gilt durch Reduktion die Untergrenze auch für unser Problem.O(n∗logn)
quelle