3.3.1 Iso-orientierte Segmente

Das ist der Inhalt von Praktikumsaufgabe 2.

Problem (Folie 13)

Eingabe	Menge $S$ von $n$ waagrechten und senkrechten Segmenten
Ziel	alle Paare von Segmenten aus $S$, die sich schneiden

Zwei waagrechte (oder zwei senkrechte) Segmente schneiden sich in allgemeiner Lage nie. Es geht also nur um Paare (senkrecht, waagrecht).

Wie viele Schnitte kann es geben? (Folie 14)

Maximal, wenn die Hälfte senkrecht und die Hälfte waagrecht ist und sich alle kreuzen (ein Gitter): $\left(\frac n2\right)^2 = \frac{n^2}{4}$ Schnitte. Die Ausgabe kann also quadratisch groß sein.

Vereinfachende Annahme (Folie 14)

Alle Start- und Endpunkte der waagrechten Segmente und alle senkrechten Segmente haben paarweise verschiedene $x$-Koordinaten.

Damit fallen nie zwei Ereignisse auf dieselbe $x$-Position, und man muss sich keine Gedanken über die Reihenfolge gleichzeitiger Ereignisse machen.

Beobachtung 1: drei Arten von Ereignissen (Folie 15)

Nur die $x$-Koordinaten zählen. Es gibt genau drei Ereignistypen:

1. linker Endpunkt eines waagrechten Segments → Segment wird aktiv,
2. rechter Endpunkt eines waagrechten Segments → Segment wird tot,
3. ein senkrechtes Segment → es ist nur für diesen einen Moment aktiv. Es schneidet genau die aktiven waagrechten Segmente, deren $y$ in seinem $y$-Intervall liegt.

Der Status $L$ enthält also nur waagrechte Segmente, sortiert nach ihrem $y$-Wert. Der ändert sich nie, weil waagrechte Segmente konstante Höhe haben.

Algorithmus 1 (Folie 16)

 1: Initialisiere Q mit allen Ereignissen, sortiert nach x;
 2: L = ∅;  // aktive waagrechte Segmente, sortiert nach y
 3: while (Q nicht leer) {
 4:   Nimm nächstes Ereignis p aus Q und entferne es;
 5:   if (p ist linker Endpunkt des waagrechten Segments s) {
 6:     Füge s in L ein;
 7:   } else if (p ist rechter Endpunkt des Segments s) {
 8:     Entferne s aus L;
 9:   } else {  // p ist senkrechtes Segment s von (x, yl) bis (x, yu)
10:     Bestimme alle t in L mit t.y ∈ [yl, yu]
        und melde jeweils das Paar (t, s);
11:   }
12: }

Zum Durchklicken (Beispiel nach Folie 17, Schnittpaare $(B,A)$, $(C,A)$, $(C,D)$):

Schritt 1/10: Zeile 1: Q = alle Ereignisse nach x sortiert: A@2, B@4, E@6, D@8, E@9, C@11, A@12, D@13. L = ∅.

langsamnormalschnellsehr schnell

Sweep-Line Laktiv (in L)aktuelles EreignisSchnittpunkt

Das Folienbeispiel als Tabelle

$x$	Ereignis	$L$ danach (nach $y$)	Ausgabe
2	A beginnt	A	–
4	B senkrecht, $y\in[4,8]$	A	(B,A)
6	E beginnt	E, A	–
8	D beginnt	E, D, A	–
9	E endet	D, A	–
11	C senkrecht, $y\in[2,7]$	D, A	(C,A), (C,D)
12	A endet	D	–
13	D endet	∅	–

Datenstruktur für $L$ (Folien 18–19)

$L$ braucht drei effiziente Operationen:

• Einfügen eines waagrechten Segments mit Schlüssel $y$,
• Löschen,
• Bereichsanfrage (range_search): alle Elemente mit Schlüssel in $[y_l,y_u]$ ausgeben.

Lösung: ein balancierter binärer Suchbaum (AVL-Baum, Rot-Schwarz-Baum, …, siehe Anhang). Einfügen und Löschen kosten $O(\log|L|)$.

Bereichsanfrage im Suchbaum (Folien 19–22)

1. Suche den Knoten $p$ mit dem kleinsten Schlüssel $\ge y_l$.
2. Ist sein Schlüssel $\le y_u$, gib ihn aus.
3. Laufe von $p$ aus in In-Order-Reihenfolge (links – Wurzel – rechts) weiter, also immer zum Nachfolger (successor), und gib alles aus, solange der Schlüssel $\le y_u$ ist.

Algorithmus 2: Finde Knoten p mit kleinstem Schlüssel ≥ y
 1: p = root; q = NULL;
 2: while (p != NULL && p.key != y) {
 3:     q = p;
 4:     if (y < p.key) p = p.left;
 5:     else           p = p.right;
 6: }
 7: if (p != NULL) return p;        // key == y gefunden
 8: if (root == NULL) return NULL;   // leerer Baum
 9: if (q == root)                   // nur ein Knoten
        return (y <= root.key) ? root : NULL;
10: if (y < q.key) return q;
11: else           return successor(q);

Warum Zeilen 10–11? Die Suche endet an einem Blatt $q$, unter das $y$ eingefügt würde. Ist $y<q.\text{key}$, ist $q$ selbst der kleinste größere Schlüssel. Sonst ist es der In-Order-Nachfolger von $q$.

Beispiel (Folie 21–22): Baum mit den Schlüsseln 3, 4, 5, 7, 10, 12, 15, 20, 22, 23, Anfrage $[8,21]$. Die Suche nach 8 landet bei 7, also startet man bei successor(7) = 10. Danach folgen über die Nachfolger-Zeiger 12, 15, 20. Der nächste Nachfolger 22 ist $>21$, also Schluss. Ausgabe: 10, 12, 15, 20.

Nachfolger-Zeiger

Speichert man in jedem Knoten einen Zeiger auf den In-Order-Nachfolger (successor links), kostet jeder Nachfolger-Schritt $O(1)$. Ohne die Zeiger kostet ein einzelner Schritt im Worst Case $O(\log n)$, über die ganze Traversierung amortisiert aber trotzdem $O(r+\log n)$.

Laufzeit (Folie 23)

Bereichsanfrage mit $r$ Treffern:

• Suche nach $y_l$: $O(\log n)$
• Traversieren bis zum ersten Schlüssel $>y_u$: $O(r)$
• zusammen $O(\log n + r)$

Gesamter Sweep:

Teil	Aufwand
Ereignisse sortieren	$O(n\log n)$
Ereignis $p_i$ bearbeiten	$O(\log n + r_i)$, $r_i$ = Schnitte bei $p_i$
Summe über alle $\le 2n$ Ereignisse	$O(n\log n + R)$ mit $R=\sum r_i$

Ergebnis

Alle $R$ Schnittpaare von $n$ iso-orientierten Segmenten lassen sich in $O(n\log n + R)$ berechnen.

Bemerkungen (Folie 24)

• Wächst $R$ subquadratisch, ist der Sweep dem naiven $\Theta(n^2)$-Ansatz überlegen.
• Man kann zeigen: Im Worst Case braucht jedes Verfahren $\Omega(n\log n + R)$ Schritte.
• ⇒ Der Sweep für iso-orientierte Segmente ist worst-case-optimal.

(Ergänzung) Die untere Schranke setzt sich zusammen aus $\Omega(R)$ für die Ausgabe und $\Omega(n\log n)$ aus einer Reduktion: Schon zu entscheiden, ob überhaupt ein Schnitt existiert, ist so schwer wie das Element-Uniqueness-Problem.

Sonderfälle in der Implementierung (Ergänzung, wichtig für Abgabe 2)

Fall	Was tun?
Senkrechtes Segment hat dieselbe $x$-Koordinate wie ein Endpunkt eines waagrechten	Reihenfolge der Ereignisse festlegen: erst Starts, dann senkrechte, dann Enden. Dann zählen Berührungen an den Enden als Schnitt
Zwei waagrechte Segmente mit gleichem $y$	Schlüssel nicht nur $y$, sondern $(y,\text{id})$, sonst überschreibt der Baum Einträge (z.B. std::multimap oder std::set<pair<double,int>>)
Senkrechte Segmente mit gleicher $x$-Koordinate	unproblematisch, sie werden nacheinander abgefragt
Segment mit Länge 0	als senkrechtes Segment behandeln, oder vorher herausfiltern

Skizze in C++ mit std::multimap als balanciertem Baum

struct HSeg { double x1, x2, y; int id; };
struct VSeg { double x, y1, y2; int id; };

std::vector<std::pair<int,int>> isoIntersections(const std::vector<HSeg>& H,
                                                 const std::vector<VSeg>& V)
{
    enum Kind { START = 0, VERT = 1, END = 2 };   // Reihenfolge bei gleichem x
    struct Event { double x; Kind kind; int idx; };
    std::vector<Event> Q;
    for (int i = 0; i < int(H.size()); ++i) {
        Q.push_back({H[i].x1, START, i});
        Q.push_back({H[i].x2, END, i});
    }
    for (int i = 0; i < int(V.size()); ++i) Q.push_back({V[i].x, VERT, i});
    std::sort(Q.begin(), Q.end(), [](const Event& a, const Event& b) {
        return a.x < b.x || (a.x == b.x && a.kind < b.kind);
    });

    std::multimap<double, int> L;                     // y -> Index des waagrechten Segments
    std::vector<std::multimap<double,int>::iterator> pos(H.size());
    std::vector<std::pair<int,int>> out;
    for (const Event& e : Q) {
        if (e.kind == START)    pos[e.idx] = L.insert({H[e.idx].y, e.idx});
        else if (e.kind == END) L.erase(pos[e.idx]);
        else {                                          // range_search
            const VSeg& v = V[e.idx];
            for (auto it = L.lower_bound(v.y1); it != L.end() && it->first <= v.y2; ++it)
                out.push_back({v.id, H[it->second].id});
        }
    }
    return out;
}

lower_bound ist genau Algorithmus 2 („kleinster Schlüssel ≥ $y_l$“), ++it ist successor.