Kürzester Abstand zwischen einem Punkt in A und einem Punkt in B.

9

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 .ABnABmin { dist(p,q) | pAqB }

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 O(n) im zweidimensionalen Raum gelöst werden kann.

com
quelle
4
Was ist die Frage hier?
Raphael
Ich bin kein Experte, aber normalerweise im maschinellen Lernen, wo diese Punkte Daten sind, die Mengen sich die meiste Zeit gut verhalten und zusammen gruppiert sind, so dass Algorithmen wie der von @Pedro vorgeschlagene gut funktionieren.
Chazisop
2
"was offensichtlich durch LP in O (n) im zweidimensionalen Raum gelöst werden kann" - ich frage mich, was diese Aussage veranlasst hat. "Lineare Programmierung" ist im Allgemeinen nicht in linearer Zeit lösbar; das "lineare" bezieht sich auf etwas anderes. Hat die LP also eine besondere Form?
Raphael

Antworten:

4

Ich habe eine Lösung, die etwas kompliziert erscheint, aber effizienter sein sollte als die naive Brute-Force-Suche:O(n2)

  1. lassen sein die Achse zwischen den Mitten der Masse von und .vAB
  2. Sortieren Sie die Punkte in und entlang dieser Achse in absteigender bzw. aufsteigender Reihenfolge, was zu den Sequenzen , , ..., und , , ..., .ABa0a1anb0b1bn

Der Rest ist in Pseudocode, um es klarer zu machen:

d = infinity.
for j from 1 to n
    if (b_1 - a_j) along v > d then break endif
    for k from 1 to n
        if (b_k - a_j) along v > d then
            break
        else
            d = min( d , ||b_k - a_j|| )
        endif
    enddo
enddo

Das heißt, indem Sie die Punkte entlang vorsortieren , können Sie Paare herausfiltern, die niemals innerhalb von voneinander liegen, da entlang immer.vdbkajvbkaj

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)ABO(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

Pedro
quelle
2
@ Pedro: Entschuldigung, ich habe nicht früher kommentiert (keine Zeit zu der Zeit). Der Grund, warum ich Ihre Antwort abgelehnt habe, war, dass es eine schlechte Antwort war und nicht oben stehen sollte. Dies ist tatsächlich ein bekanntes Problem in der Berechnungsgeometrie mit dem ungünstigsten Fall O (n log n). Eine gute Antwort hätte auf das bekannte Problem (möglicherweise mit einer Referenz) und die gängigen Lösungen hingewiesen, zu denen gehören: Verwenden von kd-Bäumen und Testen elementweise, Sweep-Algorithmen usw. Die allgemeine Idee sollte darin bestehen, in einer geordneten Struktur vorzuverarbeiten und diese zu verwenden . Schauen Sie sich den 1D-Fall an - dort ist O (n log n) offensichtlicher.
ex0du5
2
@ ex0du5: Das klingt so, als ob du deine eigene Antwort posten solltest! Beachten Sie, dass "es gibt eine bessere Antwort" normalerweise kein guter Grund für eine Ablehnung ist. Diese Maßnahme sollte für falsche, Spam- und sehr schlecht formatierte Antworten reserviert werden. Pedro ist keiner. Sehen Sie auch hier, um einen Eindruck davon zu bekommen, wie viel Gedanken einige Leute vor einer Abstimmung haben sollten.
Raphael
1
@ Raphael: Ich habe nicht geantwortet, weil es eine faire Antwort gab und ich keine Zeit hatte, Referenzen nachzuschlagen. Was Ihre Referenz zum Downvoten betrifft, so ist dies ein schrecklicher Algorithmus für diese Websites! Insbesondere CS-Studenten sollten verstehen, wie wichtig es ist, das Ziel für den Formalismus nicht zu verlieren. Das Ziel der Abstimmung ist es, Antworten in ein Ranking zu verschieben, das spätere Schüler desselben Problems zu den nützlichsten Antworten führt. Mein Algorithmus für die Abstimmung macht das. Das Algo: offensichtlich nicht. Dies kann auf einem Meta diskutiert werden, wenn Sie möchten, aber als Erwachsene sollten wir unsere Kräfte für immer einsetzen, denke ich.
ex0du5
1
@ ex0du5: Du scheinst jetzt etwas Zeit zu haben. Können Sie tatsächlich zeigen, dass diese Instanz tatsächlich ein "bekanntes Problem mit dem schlimmsten Fall " ist? O(nlogn)
Pedro
1
@ ex0du5: Tatsächlich hat die Suche nach dem nächsten Nachbarn, z. B. unter Verwendung von kd-Bäumen , nur eine durchschnittliche Komplexität O (logn) . Also sind wir wieder auf dem ersten Platz.
Pedro
4

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.

Artium
quelle
2
Nur eine Bemerkung, man kann auch den klassischen Divide and Conquer-Algorithmus für engste Paare anpassen, der ebenfalls in läuft ; siehe auch Wikipedia . O(nlogn)
Rizwanhudda
1
Für einen randomisierten linearen Zeitalgorithmus siehe beispielsweise Rabin wirft eine Münze in Liptons Blog.
Juho
3
Könnten Sie etwas genauer sagen, wie Sie dies für disjunkte Mengen implementieren würden, insbesondere im Hinblick auf die Beibehaltung der -Bindung? O(nlogn)
Pedro
-1 für Unrichtigkeit. Der nächstgelegene Paar-Zeilenumbruch-Algorithmus, den Sie verknüpfen, basiert auf der sortierten Menge, die -Elemente enthält. Bei disjunkten Mengen enthält diese Menge jedoch zunächst Elemente, sodass sie sich nicht mehr in befindet Zumindest nicht im schlimmsten Fall. O(1)nO(nlogn)
Pedro
1
@ Pedro: Warum sollte es größer sein? Wenn überhaupt, sollte der Satz der aktuellen Kandidatenpunkte schrumpfen.
Raphael
4

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:

  1. Nehmen Sie Set A und erstellen Sie die effiziente Abfragestruktur für den nächsten Nachbarn Ihrer Wahl. Dieser Konstruktionsschritt ist O (n log n) [siehe Satz 4].
  2. Fragen Sie für jedes Element in B die Struktur A nach dem nächsten Nachbarn ab. Jede Abfrage ist O (log n) [siehe Satz 15, feste Dimension], daher beträgt die Gesamtabfragezeit für alle Punkte in B O (n log n).
  3. Wenn das Ergebnis für den nächstgelegenen Punkt in A zu jedem B abgerufen wird, legen Sie es in eine nach Entfernung geordnete Struktur. Dies ist O (log n), um jedes Ergebnis einzufügen, oder O (n log n) für alle.
  4. Wenn alle B betrachtet wurden, können Sie schnell (O (1)) den Punkt B in der geordneten Struktur mit dem kleinsten Nachbarabstand zu einem Punkt in A erhalten.

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.

ex0du5
quelle
1
"Die Lösung von Artium kann beispielsweise in dieser Form geschrieben werden und ist vollständig gültig." - Nun, was Sie hier vorschlagen, ist kein (reiner) Sweep-Line-Algorithmus mehr, also weiß ich nichts darüber.
Raphael
@ Raphael: Sicher ist es. Sweepline-Algorithmen verarbeiten die Punkte wie hier beschrieben zu einer geordneten Struktur vor. Ich habe unter seiner Antwort sogar auf den Fortune-Algorithmus verwiesen, der zeigt, dass der Sweepline-Algorithmus nur eine Instanz des Voronoi-Algorithmus ist. Der Grund, warum ich die Lösung für die Abfragestruktur generisch gehalten habe, ist, dass eine große Anzahl von geometrischen Mechanismen dafür entwickelt wurden.
ex0du5
Sie benötigen keine bestimmte Reihenfolge, während Sie über iterieren , während die Reihenfolge für (viele / alle?) Sweepline-Algorithmen (daher der Name, denke ich) wesentlich ist. B
Raphael
1

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 im zweidimensionalen Raum gelöst werden kann.

Die Untergrenze für dieses Problem ist unter dem algebraischen Entscheidungsbaummodell. Ich werde hier eine grobe Skizze des Beweises geben.O(nlogn)

Wir werden die Instanz des Elementunterscheidungsproblems E auf C reduzieren.

  • Eingabe in E: S={a1,a2,a3,...,an}
  • Sei > 0 ein kleiner Bruchϵ
  • A = ,{(ai,0):1in}B={(ai+ϵ):1in}
  • Wenn wir nun den kürzesten Abstand (d) zwischen den Mengen A und B finden können, können wir das Problem der Elementunterscheidbarkeit in zusätzlicher -Zeit wie folgt entscheiden O(n)
    • Die Menge hat genau dann ein Duplikat, wenn d =Sϵ

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(nlogn)

Rizwanhudda
quelle