Effizienter Algorithmus für die Eindämmung von Rechtecken

Gegeben eine Reihe von $n$ Intervalle auf einer Linie gibt es eine $O(n \log n)$ Algorithmus zum Finden von Intervallen, die in anderen Intervallen enthalten sind (z. B. Manber, "Using Induction to Design Algorithms", 1988). Gibt es ein $O(n \log n)$ Algorithmus für achsenausgerichtete Rechtecke in höheren Dimensionen?

Ich habe im Internet gesucht und versucht, selbst darüber nachzudenken, konnte aber keine Verallgemeinerung für höhere Dimensionen finden. Zum Beispiel gegeben $n$ Bei achsenausgerichteten Rechtecken in der Ebene besteht die Aufgabe darin, herauszufinden, welche Rechtecke in anderen Rechtecken enthalten sind.

algorithms computational-geometry John Donn
quelle

Ein Ansatz, um eine Lösung für ein n + 1-dimensionales Problem abzuleiten, besteht darin, eine n-dimensionale "Ebene" durch den relevanten Raum zu " streichen "; Eine andere besteht darin, letztere durch eine solche Ebene zu unterteilen, das Problem rekursiv für diejenigen Objekte zu lösen, die die Teilungsebene nicht schneiden, und eine andere für diejenigen, die dies tun, und die Ergebnisse zusammenzustellen.

Graubart

@vzn und DW: Die Frage wurde bearbeitet. Es scheint mir auch, dass der erste Kommentar (Greybeards) zu einem effizienten Algorithmus führt (einer vertikalen "Sweeping-Linie", deren Schnittpunkte mit den Rechtecken an "Bifurkationspunkten", die Projektionen der vertikalen Seiten der Rechtecke sind, strukturelle Änderungen erfahren).

John Donn

@vzn ist das die "natürliche Verallgemeinerung", an die du gedacht hast? Wenn nicht, könnten Sie vielleicht eine Antwort posten.

John Donn

"Es scheint mir auch, dass der erste Kommentar (Greybeards) zu einem effizienten Algorithmus führt." - obwohl ich es versuchte, konnte ich keine geeignete Datenstruktur finden, um die Schnittpunkte der vertikalen Sweeping-Linie mit den Rechtecken beizubehalten (so dass Die insgesamt erforderlichen Operationen sind little_o (n ** 2).

John Donn

Antworten:

Haben Sie mehrdimensionale Indizes berücksichtigt? Sie sind normalerweise sehr effizient, um überlappende oder eingeschlossene Rechtecke zu finden.

Ich persönlich habe eine Art Präfix-Sharing-Binärquadtree geschrieben: Java-Quellen Es gibt eine API für Rechtecke mit einer speziellen Methode zum Suchen von Rechtecken, die in einem anderen Rechteck enthalten sind : PhTreeSolidF.queryInclude().

Ich bin mir nicht sicher, wie komplex es ist, aber es liegt ungefähr in der Größenordnung von O (n * k * log n), den Baum und O (k * log n) für jede Abfrage zu erstellen (k ist die Anzahl der Dimensionen). Bei stark gruppierten Datensätzen kann es sogar zu einem Verlust von O (1) für jede Abfrage kommen (ich habe dies mit n = 10.000.000 und 2 <= k <= 15 getestet).

TilmannZ
quelle

-1

Es gibt eine natürliche Erweiterung / Verallgemeinerung des Bereichs, der nach achsenausgerichteten Rechtecken und höherdimensionalen Hyperwürfeln sucht.

Das Problem reduziert sich darauf, den Bereichseinschluss auf jeder Achse separat zu überprüfen und dann den Schnittpunkt der Rechtecke oder Hyperwürfel zu finden, die jeden 1-d-Bereichseinschluss "besitzen". Es dauert k * O (f (n)), wobei f (n) die Zeit ist, um eine einzelne Dimension zu überprüfen, und k die Anzahl der Dimensionen ist. Dies basiert auf der einfachen Idee, dass sich bei achsenausgerichteten Rechtecken / Hyperwürfeln ein Hyperwürfel in einem anderen Hyperwürfel befindet, wenn sich auch alle seine separaten Seiten befinden. Dies bestimmt nicht nur überlappende achsenausgerichtete Rechtecke / Hyperwürfel, obwohl ein ähnlicher Algorithmus dies kann.

Ich bin mir dessen in der Literatur nicht bewusst, aber es ist nicht komplex und vermutlich wird es zumindest nebenbei irgendwo zitiert. Die Literatur zu diesem Thema arbeitet im Allgemeinen mit Kd-Bäumen oder Quadtrees (2. Fall) und fällt in die allgemeine Kategorie der Datenbankbereichsabfrage / -suche . Der Ansatz dort wäre im Allgemeinen, die Definition allgemeiner geometrischer Objekte wie Polygone zu ermöglichen und dann alle Knoten im Kd zu finden, mit denen sich das Polygon überlappt, und die Bereichsberechnung über alle Knoten des Polygons (der Polygone) durchzuführen, um Schnittpunkte zu bestimmen.

vzn
quelle

Ich habe das Gefühl, Sie beschreiben eine

O (k * n^{2})

$O(k*n^2)$ Algorithmus hier. Was schlimmer ist als das, was das OP verlangt. Ein wichtiger Punkt ist, was die Ausgabe Ihrer Überprüfung für jede Dimension ist. Markiert es nur die Einträge, die von etwas abgedeckt werden , ODER ist es eine Aufzeichnung darüber, welche Einträge welche abdecken? Denn wenn es das erstere ist, denke ich nicht, dass Informationen ausreichen, um die Ergebnisse jeder Dimension zu kombinieren. Sie müssen die Identität des Deckungseintrags kennen. In der letzteren Version, in der Sie die Identität des Deckungseintrags aufzeichnen, wird Zeit benötigt

O (n^{2})

$O(n^2)$ für jedes D wie ich denken kann.

Apiwat Chantawibul

stimmte zu, dass die Komplexitätsanalyse nicht trivial und nicht detailliert / ausgefüllt ist, sondern für "nah" gehalten wird. Die Einschlüsse im 1d-Bereich können als Baum für die Beziehung "A innerhalb von B" dargestellt werden. könnte den Code irgendwann in Rubin mit einer weiteren Neigung schreiben. kann Details im Computer Science Chat für jeden mit der Zeit

klären