80 lines
2.8 KiB
TeX
80 lines
2.8 KiB
TeX
\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}
|