# 25 Geometrie III - Rechtecksschnitt

[TOC]

[comment]: # (Zuerst ein paar LaTeX-Makros:)

$\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\O}{\mathcal{O}}$

*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).

## Einführung

Wo wir gestern stehen blieben: Wir wollen das Detektionsproblem für den Schnitt von achsenparallelen Rechtecken beantworten. Wir haben bereits unseren Scanline-Ansatz fixiert und auf folgendes Problem reduziert: Für Punkte in der Ebene (wobei jeder Punkt ein Intervall darstellt) wollen wir für rechteckige Anfragebereiche wissen wie viele Punkte darin liegen.


## Range Trees
*Aufgabe:* Finde alle Punkte in einem Anfragerechteck!

Wir suchen also eine Datenstruktur, welche eine dynamische Punktmenge verwalten kann und Bereichsanfragen unterstützt.

Bevor wir uns unserem 2-dimensionalen Fall widmen, überlegen wir es uns für nur eine Dimension. Für Punkte entlang des Zahlenstrahls wollen wir Bereichsanfragen unterstützen. Das haben wir schonmal gemacht! Ein AVL-Baum mit doppelt verketteter Elementliste unterstützt dies. Wir suchen nach dem linken Intervallende und gehen dann solange zum rechten Nachbar, bis wir das Intervall verlassen. Das ergibt die Laufzeit $\O(\log n + k)$, wobei $k$ die Anzahl Punkte im Intervall, also die Outputgrösse, ist. So einen Baum, der einfach ein AVL-Baum mit Blattverkettung ist, nennt man auch Bereichsbaum oder *Range-Tree*.

Und in 2D? Geht es mit zwei separaten AVL-Bäumen, einen nach $x$, einen nach $y$? Es ist unklar, wie wir die Punktemengen nach $x$ mit der Menge nach $y$ effizient schneiden würden. Wenn wir nur einen Range-Tree nach $x$-Koordinate benutzen und dann alle gefundenen Punkte händisch nach der $y$-Koordinate überprüfen, verlieren wir sämtliche Laufzeitgarantien und sind nicht mehr besser als die naive $\O(n)$-Lösung. Es ist also nicht ganz einfach.

### 2D-Idee
Was in 2D funktioniert ist folgendes: Wir nehmen die Idee des Schirms, die wir schon beim Zählen von orthogonalen Linienschnitten gesehen haben. Wir bauen uns einen Range-Tree nach $x$ und suchen dann nach den beiden Intervallrändern nach $x$-Richtung. Dies gibt uns den Schrim in der Form von $\leq 2 \log n$ Teilbäumen, die alle Punkte enthalten, welche im gewünschten $x$-Bereich liegen. Hier ein Beispiel mit dem Schirm gelb markiert:


Beim Zählen der Linienschnitte, haben wir uns für jeden Teilbaum die Grösse gemerkt, sodass wir mit Hilfe dieses sogenannten Aggregatwertes aus dem Schirm rasch die Bereichsgrösse bestimmen konnten. Nun brauchen wir etwas mehr: Für das Aggregat in jedem Knoten dieses $x$-Range-Trees genügt nun ein einzelner Wert nicht, denn wir müssen für jeden Teilbaum eine Bereichsanfrage nach $y$ unterstützen. Das erzielen wir indem wir in *jedem* Knoten des $x$-Range-Trees einen kompletten $y$-Range-Tree speichern, der die selben Punkte enthält wie der Teilbaum im $x$-Range-Tree, aber eben nach $y$-Koordinate sortiert. Diese Skizze illustriert die Idee. Die gestrichtelten Pfeile verweisen jeweils auf den sekundären $y$-Range-Tree, der zum Teilbaum gehört. Explizit gezeichnet sind nur diejenigen Sekundärbäum im Schrirm des Intervalls $[l,r]$.


### Analyse
Eine Bereichsanfrage entspricht also nicht nur einer, sondern vielen Bereichsanfragen in unserer Datenstruktur, eine Anfrage pro Teilbaum im Schirm. Damit ergibt sich die Laufzeit $\O((\log n)^2 + k)$.

Für den Speicherplatzbedarf überlegen wir uns in wievielen sekundären $y$-Range-Trees jeder Punkt gespeichert wird: Da dies $\log n$ viele sind, ist der Platzbedarf $\O(n \log n)$.

### Dynamik
Wie unterstützen wir die Dynamik, also das Einfügen und Entfernen von Punkten? Fügen wir einen neuen Punkt ein, so suchen wir zuerst im primären Baum gemäss der $x$-Richtung. Für jeden Knoten, dem wir auf diesem Einfügepfad begegnen, müssen wir den neuen Punkt in seinem sekundären $y$-Range-Tree einfügen. Also selbst wenn wir das Rebalancieren des Primärbaumes mal ignorieren, bedeutet das also Aufwand $\O((\log n)^2)$.

Über das Rebalancieren müssten wir uns noch genauere Gedanken machen, aber das lassen wir für den Moment. In unserer Anwendung lässt sich das leicht lösen, da wir alle auftretenden $l$-Koordinaten im Voraus sammeln können und so den Baum statisch balancieren können, also ein für diese Eingabe perfekt ausgewogenes Grundgerüst unter den Range-Tree legen können.

Das Entfernen geht analog. Entlang der $\log n$ Knoten auf dem Suchpfad entfernen wir den Punkt aus deren Sekundärbäumen, also insgesamt $\O((\log n)^2)$ Aufwand.


Der Platzbedarf des Range-Trees ist noch nicht optimal. Normalerweise stört uns ein $\log$-Faktor in der Laufzeit ja nicht besonders - wir warten einfach ein wenig länger. Ein $\log$-Faktor im Speicherbedarf ist aber schon dramatischer, da wir nicht unbegrenzt Speicher zu Verfügung haben.

## Segment-Baum

### Idee
Vergessen wir nun die Punktrepräsentation von Intervallen wieder. Stattdessen wollen wir die Intervalle direkt in den Baum speichern und so die Sekundärstruktur vereinfachen. Das grosse Ziel ist also die Intervall irgendwie auf die Knoten zu verteilen, dass wir keine sekundären Bäume mehr brauchen. Geht das?

Wir betrachten einen Binärbaum in $y$-Richtung. Wir bauen ein statisches Gerüst, genannt *Skelett*, mit allen $y$-Koordinaten, die in der Eingabe auftreten. Unser Baum weiss also schon zu Beginn alle Koordinaten, die auftreten werden, und ist diesbezüglich schon perfekt balanciert. Dadurch können wir uns jegliches Rebalancieren sparen, auch wenn die verwaltete Intervallmenge dynamisch ist.

Für jedes Intervall markieren wir alle Punkte im Schirm. Jedes Intervall hinterlässt also höchstens $2 \log n$ Markierungen an genau definierten Stellen. Hier ein Beispiel mit drei Intervallen:


### Aufspiessanfragen
Können wir damit nun Überlappungsanfragen beantworten? Nein, denn nur in den Knoten des Schirms der Anfrage nachzuschauen ist nicht genau genug. Warum? Für grosse Anfrageintervalle schauen wir allenfalls nur Knoten hoch oben im Baum an und so kann es passieren, dass wir ein kleines Interval, das nur in Knoten tief unten markiert ist, übersehen.

Im Beispiel oben würde folgende Anfrage beispielsweise nur die Überlappung mit Intervall $B$ finden, die ebenfalls überlappenden Intervalle $A$ und $C$ würden hingegen übersehen.


Was wir hingegen beantworten können sind sogenannte *Aufspiessanfragen*, Anfragen nach einzelnen Punkten. Suchen wir nach einem einzelnen Punkt, so begegnen wir allen gespeicherten Intervallen, die diesen Punkt enthalten, auf dem Suchpfad nach diesem Punkt.


Können wir mit diesen Aufspiessanfragen die Intervallüberlappung simulieren? Schauen wir uns genauer an, wie sich zwei Intervalle überlappen können.


Wir beobachten: In den Fällen $II$ und $IV$ genügt eine Aufspiessanfrage nach dem linken Ende des Anfrageintervalls. Im Fall $III$ liegt das rechte Ende des Anfrageintervall im gespeicherten Intervall. Der einzig problematische Fall ist also $I$ wenn das Anfrageintervall ein gespeichertes Inverall komplett enthält. In diesem Fall genügt es aber, wenn wir eine Bereichsanfrage auf den linken Enden^[Genau so gut ginge es mit den rechten Enden.] aller gespeicherten Intervalle durchführen. Und das können wir mit einem AVL-Baum erledigen, wie wir im 1D-Fall gesehen haben. Eine Bereichsanfrage auf den linken Enden der gespeicherten Intervalle deckt auch gleich Fall $III$ ab.

### Implementierungsdetails des Segmentbaumes
Was verwenden wir als Aggregatszustand in den Knoten des Segmentbaumes? In jedem Knoten, müssen wir uns eine Menge von Intervallnamen merken.

Das geht am einfachsten mit einer doppelt verlinkten Liste. Einfügen ist dann ganz leicht und beim Aufspiessen wollen wir ja sowieso alle Intervalle in einem Knoten ausgeben, daher müssen wir nur durchlaufen können. Problematisch ist also nur das Löschen. Um effizient löschen zu können, merken wir uns in einem separaten Dictionary pro Intervall die Zeiger auf alle Listeneinträge für dieses Intervall in den Segmentbaumknoten. Beim Einfügen können wir diese Zeiger leicht sammeln und so können wir beim Löschen jeden Eintrag in konstanter Zeit aus der verlinkten Liste rauslöschen. Die Entfern-Operationen können wir alternativ auch *lazy* implementiert. Wir merken uns in einer separaten Datenstruktur die Indices der schon gelöschten Intervalle. So können wir, ähnlich wie beim Löschen aus Hashtabellen, bei einer späteren Aufspiessanfrage leicht testen, ob das gefundene Intervall noch aktuell ist und es andernfalls erst dann rauslöschen, was amortisiert auch logarithmischen Aufwand pro Intervall bedeutet. Wir löschen also das Segment erst, sobald wir ihm nach seinem Ende zum ersten Mal wieder begegnen.

### Anwendung für den Rechteckschnitt
Wie benutzen wir diese Datenstrukturen nun, um den geplanten Scanline-Algorithmus für den Rechteckschnitt konkret umzusetzen?

Wir benutzen gleichzeitig einen Intervallbaum für die Aufspiessanfragen und einen 1D-Range-Tree (=AVL-Baum) für die Bereichsanfragen.

*Ereignis*: Start eines Rechtecks $A$ mit $[u_A, o_A]$-Intervall
1. Aufspiessanfrage mit $u_A$ im Segmentbaum
2. Bereichsanfrage $[u_A, o_A]$ über untere Enden im Range-Tree
3. Trage A als $[u_A, o_A]$ im Segmentbaum ein
4. Trage A als $u_A$ im Range-Tree ein

Die Operationen 1 und 2 benötigen dabei Zeit $O(\log n + k')$, wobei $k'=$ Anzahl aufgespiesste Segmente respektive im abgefragten Bereich liegende Punkte. Schritte 3 und 4 benötigen Zeit $\O(\log n)$.

*Ereignis*: Ende eines Rechtecks $A'$ mit $[u_{A'}, o_{A'}]$-Intervall
1. Lösche $A'$ als $[u_{A'}, o_{A'}]$ aus dem Segmentbaum
2. Lösche $A'$ als $u_{A'}$ aus dem Range-Tree

Die Operationen 1 und 2 können dabei in Zeit $\O(\log n)$ implementiert werden. Die Details zum Entfernen im Intervall-Baum besprechen wir unten.

Somit ergibt sich für unseren Scanline-Rechteckschnitt-Algorithmus:
Gesamtlaufzeit: $\O(n\log n + k)$
Speicherplatz: $\O(n\log n)$

Mit dem Speicherplatz sind wir noch nicht zufrieden. Wir wollen uns noch überlegen, ob wir nicht mit linearem Speicher auskommen können?

## Intervall-Baum
Ähnlich wie der Segmentbaum basiert auch der Intervallbaum auf einem statischen Skelett. In den Knoten werden die Intervalle gespeichert, wobei wir die Intervalle nun nur noch konstant oft abspeichern möchten:
Wir speichern ein Intervall $A$ im höchstgelegenen Knoten, dessen Schlüssel in $A$ liegt. Wie vorher benötigen wir die Operationen
1. Aufspiessen?
2. Einfügen?
3. Entfernen?


**Aufspiessanfrage mit einem Punkt $p$**
Von der Wurzel aus suchen wir alle Intervalle, welche unseren Aufspiesspunkt $p$ enthalten. In jedem Knoten des Intervallbaums haben wir dabei unter Umständen sehr viele Intervalle; einige davon enthalten $p$, andere wiederum nicht.
Wie sollen wir nun diese Intervalle abarbeiten? Wir möchten möglichst nur diejenigen Intervalle betrachten müssen, welche $p$ auch wirklich enthalten. Liegt $p$ links desjenigen Intervalls $B$, welches *am meisten* nach links reicht, so wissen wir, dass sicher kein Intervall $p$ enthält. Falls $B$ aber $p$ enthält, so betrachten wir dasjenige Intervall $A$, welches am zweitweitesten nach links reicht, und so weiter, bis ein Intervall $p$ nicht mehr enthält. Gleich müssen wir auch von rechts nach links durchgehen können. Also:
- von links nach rechts: Liste der Intervalle nach linkem Endpunkt sortiert.
- von rechts nach links: Liste der Intervalle nach rechtem Endpunkt sortiert.
Wie speichern wir die sortierten Intervalle? In einem AVL-Baum!

Totale Laufzeit einer Aufspiessanfrage: Wir gehen durch $\O(\log n)$ Knoten und betrachten in jedem Knoten (fast) nur diejenigen Intervalle, welche $p$ enthalten. Total gibt es $k$ solche, womit wir eine Laufzeit von $\O(\log n + k)$ erhalten.

**Einfügen eines Intervalls $A$**
Wir gehen durch höchstens $O(\log n)$ Knoten, bis wir den obersten Knoten mit Schlüssel in $A$ finden. Dort müssen wir $A$ in zwei AVL-Bäume einfügen, was jeweils Zeit $\O(\log n)$ dauert.

**Löschen eines Intervalls $A'$**
Ähnlich wie Einfügen. Wie finden die beiden AVL-Bäume und entfernen die beiden daraus. $\O(\log n)$.

Totale Laufzeit ist nun immer noch $\O(n\log n+k)$. Der Speicherbedarf ist nun jedoch gesunken: Der Intervallbaum hat $\O(n)$ Knoten und jedes Intervall ist nur zweimal abgespeichert, alle Intervalle zusammen belegen also auch nur $\O(n)$.

## Prioritätssuchbaum

Mit einem Prioritätssuchbaum lässt sich noch eine Lösung für die 2D-Bereichsanfragen, die wir an den 2D-Range-Tree gestellt haben in Laufzeit $\O(n\log n + k)$ und Speicher $\O(n)$ realisieren. Wir sparen also einen $\log$-Faktor gegenüber Range-Tree-Lösung sowohl in Laufzeit als auch Speicherbedarf. Zudem ist die Lösung deutlich eleganter und simpler zu implementieren als alle Lösungen die wir bisher betrachtet haben.^[Alle bisherigen Lösungen haben z.B. indirekt immer einen AVL-Baum verwendet.]

Eine Schlüsselbeobachtung ist, dass wir für unsere Intervallschnittsanfrage ja nicht beliebige Rechtecke abfragen, sondern nur nach links und nach oben offene Bereiche. Es genügt also insbesonder, wenn wir folgende Anfragen beantworten können (sogenannte 1.5D-Queries):

*Wie viele Punkte liegen im $x$-Bereich $[l,r]$ und $y$-mässig oberhalb einer Gerade $u$?*


Dazu wollen wir eine Datenstruktur bauen, die sowohl ein binärer Suchbaum in $x$-Richtung als auch ein Max-Heap in $y$-Richtung darstellt. Beliebige $n$ Punkte lassen sich immer so in einem Binärbaum darstellen (think about it!) aber wir können keine Balanciertheit erzwingen.^[Zum Beispiel für die Punkte $(1,1), (2,2), (3,3), \dots$ wäre dieser Baum zwingend Pfad.] Deshalb wollen wir die Suchbaumbedingung etwas auflockern: Wir nehmen an wir kennen alle $x$-Koordinaten, die auftreten werden^[Das ist bei unseren Geometrie-Scanline-Problemen meist der Fall.], und bauen über diesen $x$-Koordinaten ein perfekt balanciertes Skelett. Nun wollen wir nicht mehr die Suchbaumeigenschaft erhalten sondern nur noch, dass ein Punkte (x,y) irgendwo auf dem Pfad zum Blatt $x$ gespeichert wird. Insbesondere heisst das, dass wir einen Punkt in diesem Prioritätssuchbaum immer noch finden können indem wir dem Weg zum $x$-Blatt entlanggehen. Da dieser Weg aber statisch, also unabhängig von den momentan im Prioritätssuchbaum gespeicherten Punkten ist, sind wir nicht mehr auf die Vergleiche mit den Punkten darüber angewiesen sondern können quasi blind den Pfad entlanglaufen.

Die Suche nach $x$-Wert 13 findet zum Beispiel den Punkt $(13,2)$ auch wenn die Punkte nicht nach $x$-Wert sortiert sind:

Beim Einfügen achten wir nun einfach darauf, dass die Heap-Bedingung erfüllt bleibt. Wollen wir $(x,y)$ einfügen und an der Wurzel steht ein $(x',y')$ mit $y > y'$, so verdrängen wir $(x',y')$ aus der Wurzelposition und drücken es entlang des Suchpfades für $x'$ nach unten. Somit finden wir $(x',y')$ auch später noch und wir können $(x,y)$ als neue Wurzel speichern. Beim Entfernen analog: Entsteht ein Loch im Baum, so ziehen wir das Kind mit dem grösseren $y$-Wert nach oben und rekursieren.

Die Magie geschieht nun bei der Anfrage $(l,r,u)$: Wir bilden den Schirm für das $[l,r]$ Intervall und geben nun in jedem Teilbaum alles aus, was $y\geq u$ erfüllt. Da alle diese Teilbäume Max-Heaps sind, geht diese Ausgabe leicht per DFS und wir betrachten höchstens eine Baumebene mehr als das was wir ausgeben. Somit ist der Aufwand pro Anfrage nur $\O(\log n + k)$.


Unser statisches Skelett hat $2n-1$ Knoten und jeder Punkt wir in nur einem Knoten gespeichert, womit wir auch den linearen Platzbedarf erzielen. Ein Prioritätssuchbaum ist somit wirklich massgeschneidert auf unseren Anwendungsfall - und lässt sich aber leider auch nicht leicht auf allgemeine Rechtecksanfragen erweitern (think about it!).