Wählen Sie Rechtecke mit maximaler Schnittfläche

Da der Schnittpunkt der achsausgerichteten Rechtecke ein achsenausgerichtetes Rechteck ist, gibt es O (N4) mögliche Schnittpunkte (O (N) -Linken, O (N) -Rechte, O (N ) Oberteile, O (N) Böden). Der naheliegende O (N ⁵ ) -Algorithmus besteht darin, alle diese zu versuchen, wobei er für jeden prüft, ob er in mindestens N - r Rechtecken enthalten ist.

Eine Verbesserung von O (N ³ ) besteht darin, alle O (N <2>) Intervalle in der X-Dimension zu versuchen und den 1D-Algorithmus in der Y-Dimension auf diesen auszuführen Rechtecke, die das angegebene X-Intervall enthalten. (Die Rechtecke müssen nur einmal sortiert werden.)

Wie groß ist N? Ich erwarte, dass ausgefallene Datenstrukturen zu einem O (N ²     

Ich denke, ich habe ein Gegenbeispiel. Nehmen wir an, Sie haben r := N-2 . I.e. Sie möchten zwei Rechtecke mit maximaler Überlappung finden. Nehmen wir an, Sie haben Rechtecke, die denselben Bereich abdecken (= maximale Überlappung). Diese beiden werden am Ende das optimale Ergebnis sein.

Jetzt müssen wir noch mehr Rechtecke konstruieren, so dass mindestens einer dieser beiden in einem Reduktionsschritt entfernt wird.

Nehmen wir an, wir haben drei Rechtecke, die sich sehr überlappen. Aber sie sind nicht optimal. Sie haben einen sehr kleinen Überlappungsbereich mit den anderen beiden Rechtecken.

Wenn Sie jetzt die Fläche für vier Rechtecke optimieren wollen, werden Sie eines der zwei optimalen Rechtecke entfernen, richtig? Oder vielleicht müssen Sie nicht, aber Sie sind sich nicht sicher, welche Entscheidung optimal ist.

Also, ich denke, dass Ihr Reduktionsalgorithmus nicht ganz korrekt ist. Atm bin ich mir nicht sicher, ob es dafür einen guten Algorithmus gibt oder in welcher Komplexitätsklasse dies gehört. Wenn ich Zeit habe, denke ich darüber nach:)

Postscript . Das ist ziemlich defekt, kann aber einige Ideen auslösen. Es ist besonders defizitär, wenn es Ausreißer in einem Quadranten gibt, die nahe der X- und Y-Achse liegen - sie werden sich gegenseitig verstärken, als ob sie beide bei 45 Grad wären und die Lösung auf eine Weise von diesem Quadranten wegdrücken Sinn.

-

Wenn r viel kleiner als N und N ziemlich groß ist, bedenken Sie Folgendes:

Finde das durchschnittliche Zentrum.
Ordne die Rechtecke in 2 Sequenzen nach (X - center.x) + (Y - center.y) und (X - center.x) - (Y - center.y), wobei X und Y die Mitte jedes Rechtecks ​​sind.

Für jede Lösung sind alle Zurückweisungsrechtecke Mitglieder von bis zu 4 Teilsequenzen, von denen jede ein Kopf oder ein Ende jeder der 2 Folgen ist. Unter der Annahme, dass N viel größer als r ist, wird die meiste Zeit beim Sortieren der Sequenzen - O (n log n) - sein.

Um die Lösung zu finden, suchen Sie zuerst nach dem Schnittpunkt, indem Sie die r Rechtecke am Anfang und Ende jeder Sequenz entfernen. Verwenden Sie diese Basisschnittmenge, um die Berücksichtigung des "Kern" -Satzes von Rechtecken, von denen Sie wissen, dass sie in der Lösung enthalten sind, zu eliminieren. Dies wird die Kreuzungsberechnungen reduzieren, um nur mit bis zu 4 * r + 1 Rechtecken zu arbeiten.

Jeder der vier Sequenzköpfe und -schwänze sollte einem Array von r Rechtecken zugeordnet sein, wobei jeder Eintrag den Schnittpunkt darstellt, der durch Schneiden des "Kerns" mit den i innersten Rechtecken vom Kopf oder Schwanz gegeben ist. Diese Vorberechnung reduziert die Komplexität des Findens der Lösung von O (r ^ 4) zu O (r ^ 3).

Das ist nicht perfekt, aber es sollte nah sein.

Defekte mit einem kleinen r werden von sinkenden Sollwerten mit etwas besseren Alternativen auf einer der beiden Achsen erzeugt. Der maximale Fehler ist wahrscheinlich berechenbar. Wenn dies ein Problem ist, verwenden Sie anstelle der einfachen "X + Y" -Differenzformel, die ich verwendet habe, eine echte Fläche-von-Nicht-Schnittpunkt-Berechnung.

Hier ist ein explizites Gegenbeispiel (mit N = 4 und r = 2) zu dem vom Fragesteller vorgeschlagenen Greedy-Algorithmus.

Der maximale Schnittpunkt zwischen drei dieser Rechtecke liegt zwischen den schwarzen, blauen und grünen Rechtecken. Aber es ist klar, dass die maximale Schnittmenge zwischen zwei dieser drei kleiner ist als die Schnittmenge zwischen den schwarzen und den roten Rechtecken.

Ich habe jetzt einen Algorithmus, der ziemlich ähnlich zu Ed Staubs oben ist, mit den gleichen Zeitschätzungen. Es ist ein bisschen anders als Ed, da es für alle r gilt

Das Gegenbeispiel von mhum zum gierigen Algorithmus ist ordentlich. Schau es dir an.

Ich versuche immer noch, mich an diese Seite zu gewöhnen. Irgendwie wurde eine frühere Antwort von mir auf zwei Sätze verkürzt. Danke an alle für ihre Beiträge, besonders an mhum, dessen Gegenbeispiel zum Greedy-Algorithmus zufriedenstellend ist. Ich habe jetzt eine Antwort auf meine eigene Frage. Ich glaube, es ist so gut wie möglich, aber die unteren Grenzen der Komplexität sind zu schwierig für mich. Meine Lösung ähnelt der von Ed Staub und liefert die gleichen Schätzungen für die Komplexität, funktioniert aber für jeden Wert von r & gt; 0.

Eines meiner Rechtecke wird durch seine untere linke Ecke bestimmt. Sei S die Menge der unteren linken Ecken. In der Zeit O (N log (N)) sortieren wir S nach den Größen der x-Koordinaten in Sx. Uns interessiert nicht die Reihenfolge in Sx zwischen zwei unteren linken Ecken mit der gleichen X-Koord. In ähnlicher Weise wird die sortierte Sequenz Sy unter Verwendung der Größen der y-Koordinaten definiert. Nun sind u1, u2, u3 und u4 nicht negative ganze Zahlen mit u1 + u2 + u3 + u4 = r. Wir berechnen, was mit dem Bereich passiert, wenn wir verschiedene Rechtecke entfernen, die wir jetzt explizit benennen. Wir entfernen zuerst den u1-großen Kopf von Sx und den u2-großen Schwanz von Sx. Sei Syx das Ergebnis der Entfernung dieser u1 + u2 Einträge von Sy. Wir entfernen den u3-großen Kopf von Syx und den u4-großen Schwanz von Syx. Man kann nun beweisen, dass eine dieser möglichen Wahlmöglichkeiten von (u1, u2, u3, u4) die gewünschte maximale Schnittfläche ergibt. (E-Mail an mich, wenn Sie eine PDF der Proofdetails wünschen.) Die Anzahl solcher Auswahlen entspricht der Anzahl der ganzzahligen Punkte im regulären Tetraeder im 4-d euklidischen Raum mit Scheitelpunkten an den 4 Punkten, deren Koordinatensumme r und für ist welche 3 der 4 Koordinaten sind gleich 0. Dies ist durch das Volumen des Tetraeders begrenzt, was eine Komplexitätsschätzung von O (r ^ 3) ergibt.

Also hat mein Algorithmus Zeitkomplexität O (N log (N)) + O (r ^ 3).

Ich glaube, das erzeugt eine perfekte Lösung. Davids Lösung ist einfacher zu implementieren und sollte in den meisten Fällen schneller sein.

Dies beruht auf der Annahme, dass für jede Lösung mindestens einer der Zurückweisungen ein Mitglied der komplexen Hülle sein muss. Das rekursive Anwenden führt zu:

Berechnen Sie eine konvexe Hülle. Sammeln Sie die Menge aller möglichen Lösungen, die von:

(Der Rumpf muss nicht wirklich das letzte Mal repariert werden.)

Wenn h die Anzahl der ursprünglichen Hüllenelemente ist, dann ist die Komplexität kleiner als h, plus die Kosten für die Berechnung des Ausgangsrumpfs. Ich gehe davon aus, dass ein Rumpf-Algorithmus so gewählt wird, dass die sortierten Daten in den Rumpfreparaturen aufbewahrt und wiederverwendet werden können.