\section{Geradenüberdeckung}
\begin{tasks}
	\item
		Eine Gerade wird hinreichend bestimmt durch zwei Punkte, durch
		die sie verläuft. Bei $n \geq 2$ können wir jede Gerade die nur einen
		Punkt überdeckt, durch eine Gerade ersetzen, die durch mindestens zwei
		Punkte verläuft.
		\points{1}
	
	\item \label{2b}
		Jede Gerade überdeckt mindestens zwei Punkte. Es gibt $n$ viele Punkte.
		Also brauchen wir maximal $n \divslash 2$ Geraden.
		\points{1}
	\item
		Eine Gerade die mehr als $k$ Punkte überdeckt ist in der Geradenüberdeckung.
		
		Angenommen wir haben eine Geradenüberdeckung $C$ bei der jede Gerade höchstens
		$k$ Punkte überdeckt.
		Wenn es eine Gerade $g$ gibt, die mehr als $k$ Punkte überdeckt und nicht in $C$
		ist, dann wird sie an maximal $k$ Punkten geschnitten, da in $C$ höchstens $k$ 
		Geraden sind.
		Das bedeutet aber, dass nicht alle Punkte, die auf $g$ sind geschnitten und 
		damit überdeckt werden.
		Das ist ein Widerspruch zur Annahme.
		Somit muss $g$ in der Geradenüberdeckung sein.
		\points{1}
	
	\item
		Unter der Annahme, dass es keine Gerade gibt, die mehr als $k$ Punkte
		enthält gilt: Für $k < \sqrt{n}$ gibt es keine Geradenüberdeckung.
		
		Angenommen jede Gerade überdeckt genau $k$ Punkte. Dann überdecken wir mit $k$ Geraden maximal $k^2$ Punkte. Da $k < \sqrt{n}$ sind das $k^2 < n$ viele Punkte und somit keine Geradenüberdeckung.
		\points{1}

		
	\newpage
	\item
		\alg*{$k$-Geradenüberdeckung}:
		\begin{enumerate}
			\item
				Ist $k \geq n \divslash 2$, gib $true$ zurück.

			\item
				Erzeuge die Menge $G$ aller Geraden, die von zwei Punkten aufgespannt werden.
				Das sind $n^2$ viele.

			\item 
				Bestimme für jede Gerade die Anzahl der überdeckten Punkte.
				Nehme die Geraden, die mehr als $k$ Punkte überdecken in die 
				Geradenüberdeckung $C$. Wir überprüfen für alle $n^2$ Geraden,
				ob sie noch weitere Punkte überdecken. Also $n^2 \cdotp n$ Überprüfungen.

			\item
				Ist $C = \emptyset$ und $k < \sqrt{n}$, gib $false$ zurück.

			\item
				Löse den Rest mit Brute Force.

				Prüfe dafür für alle $A \in \binom{G \setminus C}{k - \abs{C}}$ ob $A \cup C$ alle Punkte überdeckt. Falls ja, gib $true$ zurück, sonst gib $false$ 
				zurück.
		\end{enumerate}

		Im Worst Case finden wir keine Geraden die mehr als $k$ Punkte überdecken.
		Dann iterieren wir über alle $\binom{\abs{G}}{k}$ Mengen von Geraden.
		Da $k \geq \sqrt{n}$ gilt
		und $\abs{G} = n^2$ können wir folgende Abschätzung machen.
		\[
			\binom{\abs{G}}{k} = \binom{n^2}{k} = \binom{(\sqrt{n})^4}{k} \leq \binom{k^4}{k} 
		\]

		Wir erhalten somit eine Gesamtlaufzeit von
		\[
			\Oh\parens{n^2 + n^3 + \overbrace{\binom{k^4}{k} \cdotp n}^\text{Für jede Auswahl an Geraden alle Punkte prüfen}}
		\]
		Das liegt in FPT.
		\points{5}



\end{tasks}