Nächstes Punktpaar zwischen zwei Sätzen in 2D

Ich habe zwei Mengen von Punkten in der zweidimensionalen Ebene. Ich möchte das nächste Punktpaar so dass , und der euklidische Abstand zwischen so klein wie möglich ist. Wie effizient kann das gemacht werden? Kann es in Zeit gemacht werden, wobei?s , t s ∈ S t ∈ T s , t O ( n log n ) n = | S | + | T $S,T$$s,t$$s \in S$$t \in T$$s,t$$O(n \log n)$$n = |S|+|T|$

Ich weiß, dass es möglich ist, das nächste Punktpaar in Zeit unter Verwendung eines Standard-Divide-and-Conquer-Algorithmus zu finden , wenn ich eine einzelne Menge bekomme . Dieser Algorithmus scheint sich jedoch nicht auf den Fall von zwei Sätzen zu verallgemeinern, da kein Zusammenhang zwischen dem Abstand zwischen den beiden nächstgelegenen Punkten innerhalb von oder und dem Abstand zwischen den beiden nächstgelegenen Punkten über diese Sätze besteht.s , s ' ∈ S O ( n log n $S$$s,s' \in S$$O(n \log n)$$S$$T$

Ich dachte daran, die Menge in einem d-Baum zu speichern und dann für jedes eine Abfrage zum nächsten Nachbarn zu verwenden, um den nächstgelegenen Punkt in zu . Die Worst-Case-Laufzeit kann jedoch so schlecht sein wie die -Zeit. Es gibt Ergebnisse, die besagen, dass wenn die Punkte von zufällig verteilt sind, die erwartete Laufzeit für jede Abfrage , sodass wir einen Algorithmus mit der erwarteten Laufzeit wenn wir Es wurde garantiert, dass die Punkte zufällig verteilt sind - aber ich suche nach einem Algorithmus, der für jede Sammlung von Punkten funktioniert (nicht unbedingt zufällig verteilt).$T$$k$$s \in S$$T$$s$$O(n^2)$$T$$O(\log n)$$O(n \log n)$

Motivation: Ein effizienter Algorithmus wäre für diese andere Frage hilfreich .

Ja, dies kann sein. Bauen Sie ein Voronoi - Diagramm für T . Finden Sie dann für jeden Punkt s ∈ S , in welcher Zelle des Voronoi-Diagramms es enthalten ist. Das Zentrum dieser Zelle ist der Punkt t ∈ T , der s am nächsten liegt .$O(n \log n)$$T$$s \in S$$t \in T$$s$

Sie können ein Voronoi-Diagramm in -Zeit erstellen , und jede Abfrage (die Zelle mit s finden ) kann in O ( log n ) -Zeit ausgeführt werden, sodass die Gesamtlaufzeit O ( n log n ) -Zeit beträgt .$O(n \log n)$$s$$O(\log n)$$O(n \log n)$

Ich erweitere meinen Kommentar zu einer Antwort, da ich eine halb zufriedenstellende Antwort gefunden habe. Dies löst nur das Problem für die -Distanz. Diese Antwort ist grundsätzlich falsch.$L^1$

Diese Arbeit löst das Problem, das nächstgelegene Punktpaar in Dimensionen für den Fall zu finden, in dem die Mengen durch eine Hyperebene in O ( n log d - 1 n ) getrennt sind .$d$$O(n \log^{d-1} n)$

Für zwei Dimensionen löst dies den Fall in der Antwort, auf die Sie sich als Hauptmotivation für Ihre Frage in beziehen . Es kann auch verwendet werden, um den allgemeinen Fall des 2D-Problems in O ( n log 2 n ) zu lösen .$O(n \log n)$$O(n \log^2 n)$

Bei zwei Mengen von Punkten in 2D werden sie in den 3D-Raum eingebettet, wobei die Menge S um einige - δ z und die Menge T um δ z in z- Richtung verschoben werden . Die Wahl von δ z kann so getroffen werden, dass die Wahl des nächstgelegenen Punktpaars nicht beeinflusst wird, indem δ z kleiner als die Genauigkeit Ihrer Eingabepunkte ist (und die Genauigkeitsbits für jede Eingabekoordinate verdoppelt werden). Verwenden Sie den 3D-Algorithmus aus dem zitierten Artikel.$S, T$$S$$-\delta_z$$T$$\delta_z$$z$$\delta_z$$\delta_z$