Effiziente Algorithmen für vertikale Sichtbarkeitsprobleme

Während ich über ein Problem nachdachte, wurde mir klar, dass ich einen effizienten Algorithmus erstellen muss, der die folgende Aufgabe löst:

Das Problem: Wir erhalten einen zweidimensionalen quadratischen Kasten der Seite dessen Seiten parallel zu den Achsen sind. Wir können es von oben untersuchen. Es gibt jedoch auch horizontale Segmente. Jedes Segment hat eine ganzzahlige Koordinate ( ) und Koordinaten ( ) und verbindet die Punkte und (siehe Bild unten).m y 0 ≤ y ≤ n x 0 ≤ x 1 < x 2 ≤ n ( x 1 , y ) ( x 2 , y $n$$m$$y$$0 \le y \le n$$x$$0 \le x_1 < x_2 \le n$$(x_1,y)$$(x_2,y)$

Wir möchten für jedes Einheitensegment oben auf der Box wissen, wie tief wir vertikal in die Box schauen können, wenn wir durch dieses Segment schauen.

Formal möchten wir für .$x \in \{0,\dots,n-1\}$$\max_{i:\ [x,x+1]\subseteq[x_{1,i},x_{2,i}]} y_i$

Beispiel: Bei und Segmenten, die sich wie im Bild unten befinden, ist das Ergebnis . Schauen Sie sich an, wie tiefes Licht in die Box gelangen kann.$n=9$$m=7$$(5, 5, 5, 3, 8, 3, 7, 8, 7)$

Zum Glück für uns beide und sind recht klein und wir können die Berechnungen off-line tun.$n$$m$

Der einfachste Algorithmus zur Lösung dieses Problems ist Brute-Force: Durchlaufen Sie für jedes Segment das gesamte Array und aktualisieren Sie es bei Bedarf. Es gibt uns jedoch nicht sehr beeindruckend .$O(mn)$

Eine große Verbesserung besteht darin, einen Segmentbaum zu verwenden, der in der Lage ist, Werte auf dem Segment während der Abfrage zu maximieren und die Endwerte zu lesen. Ich werde es nicht weiter beschreiben, aber wir sehen, dass die Zeitkomplexität .$O((m+n) \log n)$

Ich habe mir jedoch einen schnelleren Algorithmus ausgedacht:

Gliederung:

1. Sortieren Sie die Segmente in absteigender Reihenfolge der Koordinate (lineare Zeit unter Verwendung einer Variation der Zählsortierung). Es ist nun zu beachten, dass, wenn ein Einheits-Segment zuvor von einem Segment abgedeckt wurde, kein nachfolgendes Segment den Lichtstrahl mehr durch dieses Einheits-Segment binden kann. Dann fegen wir eine Linie von oben nach unten.$y$$x$$x$

2. Nun führen sie einige Definitionen: -Einheit Segment ist ein imaginäres horizontales Segment auf der Schleife , deren - Koordinaten ganze Zahlen sind und deren Länge ist 1. Jedes Segment während des Durchlaufprozesses kann entweder unmarkiert (das heißt, ein Lichtstrahl geht aus dem Der obere Rand der Box kann dieses Segment erreichen) oder markiert sein (gegenüberliegender Fall). Stellen Sie sich ein Einheitensegment vor, bei dem , immer unmarkiert ist. wir uns auch die Mengen . Jeder Satz enthält eine ganze Sequenz von aufeinanderfolgenden markierten Einheitensegmenten (falls vorhanden) mit folgenden nicht markierten$x$$x$$x$$x_1=n$$x_2=n+1$$S_0=\{0\}, S_1=\{1\}, \dots, S_n=\{n\}$ $x$ Segment.

3. Wir brauchen eine Datenstruktur, die in der Lage ist, diese Segmente und Mengen effizient zu bearbeiten. Wir werden eine Find-Union-Struktur verwenden, die um ein Feld erweitert ist, das den maximalen unit-Segmentindex (Index des nicht markierten Segments) enthält.$x$

4. Jetzt können wir die Segmente effizient handhaben. Nehmen wir an, wir betrachten jetzt das te Segment in der Reihenfolge (nennen es "Abfrage"), das in beginnt und in endet . Wir müssen alle nicht markierten Einheitssegmente finden, die innerhalb des ten Segments enthalten sind (dies sind genau die Segmente, auf denen der Lichtstrahl seinen Weg beenden wird). Wir werden Folgendes tun: Erstens finden wir das erste nicht markierte Segment in der Abfrage ( Finden Sie den Repräsentanten der Menge, in der enthalten ist, und erhalten Sie den maximalen Index dieser Menge, die per Definition das nicht markierte Segment ist ). Dann wird dieser Index$i$$x_1$$x_2$ $x$$i$$x_1$$x$Wenn Sie sich in der Abfrage befinden, fügen Sie sie zum Ergebnis hinzu (das Ergebnis für dieses Segment ist ) und markieren Sie diesen Index ( Union- Mengen mit und ). Dann wiederholen Sie diesen Vorgang , bis wir alle finden nicht markierten Segmente, das heißt, neben Suche Abfrage gibt uns Index .$y$$x$$x+1$$x \ge x_2$

Beachten Sie, dass jede Find-Union-Operation nur in zwei Fällen ausgeführt wird: Entweder beginnen wir mit der Betrachtung eines Segments (was mal vorkommen kann), oder wir haben gerade ein unit-Segment markiert (dies kann mal vorkommen). Die Gesamtkomplexität ist also ( ist eine inverse Ackermann-Funktion ). Wenn etwas nicht klar ist, kann ich darauf näher eingehen. Vielleicht kann ich ein paar Bilder hinzufügen, wenn ich Zeit habe.$m$$x$$n$$O((n+m)\alpha(n))$$\alpha$

Jetzt erreichte ich "die Mauer". Ich kann mir keinen linearen Algorithmus ausdenken, obwohl es einen geben sollte. Ich habe also zwei Fragen:

• Gibt es einen linearen Zeitalgorithmus (d. H. ), der das Sichtbarkeitsproblem für horizontale Segmente löst?$O(n+m)$
• Wenn nicht, was ist der Beweis, dass das Sichtbarkeitsproblem ?$\omega(n+m)$

1. Erste nach sowohl und Koordinaten der Linien in zwei getrennten Arrays und . $x1$$x2$$A$$B$$O(m)$
2. Wir behalten auch eine Hilfs-Bit-Array-Größe , um die aktiven Segmente zu verfolgen.$n$
3. Fange an von links nach rechts zu kehren:
4. für$(i=0,i<n,i++)$
5. {
6. ..wenn mit Wert$\exists x1=i$$y$$c$ $O(1)$
7. .. {
8. .... find ( )$\max$
9. .... store ( )$\max$$O(1)$
10. ..}
11. ..wenn mit Wert$\exists x2=i$$y$$c$ $O(1)$
12. .. {
13. .... find ( )$\max$
14. .... store ( )$\max$$O(1)$
15. ..}
16. }

find ( ) kann mit einem Bit-Array mit Bits implementiert werden . Wenn wir nun ein Element zu hinzufügen oder entfernen, können wir diese Ganzzahl aktualisieren, indem wir ein Bit auf true bzw. false setzen. Nun haben Sie zwei Möglichkeiten, abhängig von der verwendeten Programmiersprache und der Annahme, dass relativ klein ist, dh kleiner als was mindestens 64 Bit oder eine feste Anzahl dieser ganzen Zahlen ist:$\max$$n$$L$$n$$long long int$

• Das niedrigstwertige Bit in konstanter Zeit zu erhalten, wird von einigen Hardware- und GCC-Komponenten unterstützt.
• Durch Konvertieren von in eine Ganzzahl Sie das Maximum (nicht direkt, aber Sie können es ableiten).$L$$O(1)$

Ich weiß, dass dies ein ziemlicher Hack ist, da es einen Maximalwert für annimmt und daher dann als Konstante angesehen werden kann ...$n$$n$

Ich habe keinen linearen Algorithmus, aber dieser scheint O (m log m) zu sein.

Sortieren Sie die Segmente nach der ersten Koordinate und Höhe. Dies bedeutet, dass (x1, l1) immer vor (x2, l2) steht, wenn x1 <x2 ist. Auch (x1, l1) in Höhe y1 kommt vor (x1, l2) in Höhe y2, wenn y1> y2.

Für jede Teilmenge mit derselben ersten Koordinate gehen wir wie folgt vor. Das erste Segment sei (x1, L). Für alle anderen Segmente in der Teilmenge: Wenn das Segment länger als das erste ist, ändern Sie es von (x1, xt) in (L, xt) und fügen Sie es in der richtigen Reihenfolge zur L-Teilmenge hinzu. Sonst lass es fallen. Wenn die erste Koordinate der nächsten Teilmenge kleiner als L ist, teilen Sie (x1, L) in (x1, x2) und (x2, L) auf. Addieren Sie die (x2, L) zur nächsten Teilmenge in der richtigen Reihenfolge. Wir können dies tun, weil das erste Segment in der Teilmenge höher ist und den Bereich von (x1, L) abdeckt. Dieses neue Segment kann dasjenige sein, das (L, x2) abdeckt, aber das werden wir nicht wissen, bis wir uns die Teilmenge ansehen, die die erste Koordinate L hat.

Nachdem wir alle Teilmengen durchlaufen haben, werden wir eine Reihe von Segmenten haben, die sich nicht überlappen. Um den Y-Wert für ein gegebenes X zu bestimmen, müssen wir nur die verbleibenden Segmente durchlaufen.

Was ist die Komplexität hier: Die Sortierung ist O (m log m). Das Durchlaufen der Teilmengen ist O (m). Ein Lookup ist auch O (m).

Es scheint also, dass dieser Algorithmus unabhängig von n ist.