# AlGeo - Zettel 3

##### Adrian Oyen, Helena Lochner, Christoph Geron

### Problem 1:
Betrachten Sie die untere Kontur einer Menge von $n$ Strahlen in der Ebene. Zeigen Sie, dass die Anzahl der Kanten der unteren Kontur in $O(n)$ ist.
(a) Betrachten Sie zunächst nur eine Menge von $n$ Strahlen die nur nach rechts gerichtet sind. Analysieren Sie die maximale Ordnung der zugehörigen Davenport-Schinzel-Sequenzen.
(b) Analysieren Sie die Anzahl der Kanten der unteren Kontur im allgemeinen Fall.

In allen folgenden Skizzen sind die Horizontalen Linien nur zum Zweck der Visualisierung anwesend.
#### Teil a)
Die maximale Ordnung der Davenport-Schinzel-Sequenz ist 2.
Wir betrachten die Strahlen nacheinander(mit Startpunkten von links nach rechts) und gehen wie bei der vollständigen Induktion vom einfachen Fall aus (nur ein Strahl bzw. nur zwei Strahlen). Bei jedem hinzukommenden Strahl gibt es verschiedene Fälle.
Fallunterscheidung:
Fall 1: Der Strahl-Startpunkt liegt über der bisherigen unteren Kontur:
- 1.1: Der Strahl schneidet die untere Kontur:
Damit erhöht sich die Anzahl der Kanten in der unteren Kontur maximal um 1, denn ab dem Schnittpunkt mit der Kontur gilt der neue Strahl solange als Kontur, bis er wieder einen Strahl schneidet (dies muss dann ein anderer Strahl sein, also kann nicht wie bei Fall 2.1 eine Kante durch drei ersetzt werden).
- 1.2: Der Strahl schneidet die untere Kontur nicht:
$\to$ Trivial $\leftarrow$

Fall 2: Der Strahl-Startpunkt liegt unter der bisherigen unteren Kontur
- 2.1: Der Strahl schneidet die untere Kontur:
Damit erhöht sich die Anzahl der Kanten in der unteren Kontur um maximal 2, denn falls der Startpunkt weiter rechts auf der x-Achse liegt, kommt es zu 2 Wechseln der Strahlen in der unteren Kontur. (siehe Skizze)
- 2.2: Der Strahl schneidet die untere Kontur nicht:
Ab dem Startpunkt ist der Strahl die neue untere Kontur und somit ist die untere Kontur wieder um maximal eins erhöht.

Skizze für Fall 2.1(Die neue Kante ist mit rot markiert)

Damit kann es mit jedem neuen Strahl zu maximal linear vielen neuen Kanten in der unteren Kontur kommen. Damit folgt die Anzahl der Kanten in der unteren Kontur liegt in $O(n)$.

#### Teil b)
Unter Betrachtung aller Eventualitäten ist dies der Worst Case:

Die Schlussfolgerung drängt sich auf, dass pro weiterem Strahl maximal 3 Kanten zu der unteren Kontur hinzukommen.
Dies ist linear somit liegt die obere Schranke in $O(n)$.

### Problem 2:
Gegeben sei eine Sequenz $X$ von $n$ paarweise verschiedenen, aufsteigend sortierten, reellen Zahlen $x_1 < · · · < x_n$ und ein Intervall $[a, b] \subset\mathbb{R}$. Betrachten Sie das Entscheidungsproblem: $X \cap [a, b] = \emptyset$ ?
(a) Nehmen Sie an, dass $x_{i+1} − x_i > b − a$ für alle $1 ≤ i ≤ n$. Zeigen Sie, dass unter dieser Annahme das Entscheidungsproblem die Komplexität $\Omega(log(n))$ im linearen Modell hat.
(b) Zeigen Sie eine untere Schranke für das Entscheidungsproblem im linearen Modell ohne die Annahmen aus Teilaufgabe (a).

#### Teil (a)

*Idee:*
Um zu entscheiden, ob ein Punkt von $X$ innerhalb des Intervalls liegt, können wir nutzen, dass die Punkte bereits sortiert sind. Außerdem wissen wir durch die Einschränkung, dass nur maximal ein Punkt in dem Intervall liegen kann, da die Abstände zwischen den $x_i$ größer sind als der Abstand zwischen $a$ und $b$.
Wir müssen für die Punkte, die wir betrachten, überprüfen, ob sie zwischen $a$ und $b$ liegen. Dies können wir in zwei Vergleichen im linearen Modell machen. Damit wir nicht alle Punkte überprüfen müssen, fangen wir in der Mitte an, also beim Punkt $x_{n\backslash2}$. Falls es eine gerade Anzahl Punkte gibt, können wir uns dabei entscheiden, auf- oder abzurunden (welches davon wir nehmen spielt keine Rolle). Nun überprüfen wir die beiden Fälle, nämlich...
1. ...ob der Punkt größer als $b$ ist. Falls ja, ist der Punkt außerhalb des Intervalls und alle größeren Punkte (also in der rechten Hälfte) ebenfalls. Somit müssen wir nur noch die linke Hälfte betrachten. Wir gehen direkt zu deren mittlerem Punkt (z.B. $x_{n\backslash4}$) über und beginnen wieder von vorn mit dem Vergleichen. Falls der Punkt kleiner als $b$ ist, gehen wir dazu über...
2. ...zu prüfen, ob der Punkt kleiner als $a$ ist. Falls ja, liegt er nicht im Intervall und wir müssen nun (gespiegelt zu 1.) nur noch die Punkte rechts davon betrachten, denn alle Punkte weiter links sind dann ebenfalls zu klein. Wir gehen also zum mittleren Punkt der linken Hälfte (z.B. $x_{3n\backslash4}$) über und fangen wieder von vorne an mit dem Vergleichen. Falls der Punkt größer als $a$ war, haben wir einen Punkt im Intervall gefunden und können terminieren.

*Komplexität:*
Bei jedem Neuanfang des Algorithmus (siehe die 2 Schritte) wird die noch zu betrachtende Punktmenge halbiert. Somit muss der Algorithmus nur maximal $2\log(n)$ Schritte durchlaufen (wegen der zwei Vergleiche mit $a$ und $b$), bevor er entweder terminiert, weil er einen Punkt im Intervall gefunden hat oder weil keine weiteren Punkte übrig bleiben. Daraus begründet sich die Komplexität von $\Omega(\log(n))$.

*Entscheidungsbaum:*
Der Entscheidungsbaum terminiert mit einem Ja in dem Fall, dass der Nenner $\geq n$ wird.

#### Teil (b)

Da wir die Beschränkung in (a) nicht gebraucht haben, gilt die Untergrenze auch für (b).