Algorithmus für> 2D-Skyline Abfrage/Efficient Frontier

Question

Das Problem bei der Hand:

eine Menge von N Punkten in einem D-dimensionalen Raum gegeben, mit allen ihren Koordinaten> = 0 (in 2D die Punkte alle in der sein würden, 1. Quadrant, in 3D im 1. Oktant, und so weiter ...), entfernen Sie alle Punkte, die einen anderen Punkt haben, dessen Wert in jeder Koordinate größer oder gleich ist.

In 2D ist das Ergebnis folgendermaßen aus:

(Bild von Vincent Zoonekynd Antwort here), und es ist ein einfacher Algorithmus, detaillierter in dieser Antwort, die in N*log(N) läuft. Mit Chunking hätte ich es zu N*log(H) gebracht haben, aber Optimierungen auf das sind für eine andere Frage.

Ich war daran interessiert, die Lösung auf 3 Dimensionen bei der Verlängerung (und möglicherweise 4, wenn es noch sinnvoll ist), aber mein aktueller 3D-Algorithmus ist ziemlich langsam, umständlich und verallgemeinern nicht auf 4D schön:

• Sortier Punkte auf der x-Achse, mit Anmerkungen versehen, die Position eines jeden Punktes
• eine Art von Segmentbaum mit N Blättern initialisieren, wo Blätter werden die Punkte y-Werte halten, und ein Knoten max(child1, child2)
• Sortierpunkte auf der z-Achse halten
• Für jeden Punkt von dem größten z:
  • prüfen, welche Position sie in der x-Ordnung waren, versuchen Sie es in dem Segmentbaum
  • Check in dieser Position an erster Stelle, wenn es ein Punkt bereits nach unten ist (so hat es> z), an einer höheren Stelle (so hat es> x) mit einem größeren y (das kostet log (N), danke Baum)
  • Wenn dieser Punkt gefunden wird, wird der aktuelle Punkt verworfen, andernfalls wird er eingefügt und der Baum ist aktualisiert

Dieses Angebot läuft noch in N*log(N), aber erfordert 2 verschiedene Sorten und eine 2*N -große Struktur.

Erweiterung würde erfordern eine andere Art und eine prohibitive 2*N^2-big Quad-Struktur.

Gibt es effizientere (insbesondere CPU-bezogene) Ansätze?

---

Ich glaube nicht, es relevant ist, aber ich bin in C schreiben, der Code ist here.

Answer 1

Wenn ich dies in N-Dimensionen mache, würde ich einen k-d-Baum des nächsten Nachbarn verwenden. Der Baum ist ein schneller Weg, um Punkte basierend auf ihrer Entfernung von einem Ort im N-D-Raum zu sortieren. Standardmäßig sortiert der K-D-Baum Punkte basierend auf seiner euklidischen Distanz zu einem bestimmten Ort, indem er verschachtelte Bäume erstellt.

Es gibt eine Möglichkeit, die Entfernungsmetrik so zu ändern, dass sie genau Ihren Anforderungen entspricht. Nachdem Sie den Baum gebaut haben, wollen Sie einfach die Punkte, die am weitesten von Ihrer Herkunft entfernt sind.

euklidischen Entfernung Metric:

sqrt (sum_over_dimensions (coord ** 2))

Ich schlage vor, schlagen die Metrik (was falsch sein kann):

sum_over_dimensions (Koord)

Links:

Wiki K-D-Baum:

https://en.wikipedia.org/wiki/K-d_tree

Überlauf Beitrag über K-D-Baum-Metriken:

Can I use arbitrary metrics to search KD-Trees?

Definition mathematischer Metrik:

https://en.wikipedia.org/wiki/Metric_(mathematics)

Zusammenfassend - ich vermute, dass Sie, wenn Sie genug Zeit für das Problem aufwenden, eine robuste N-dimensionale Lösung für Ihr Problem erstellen könnten, die "Worst-Case-Komplexität von O (kn log n)" hat. [wobei k die Anzahl der Dimensionen ist] ". Ich vermute auch, dass es schwierig ist, es besser zu machen, weil großdimensionale Algorithmen für den nächsten Nachbarn ein bekanntes ungelöstes Problem sind.