\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{ngerman}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{11}
\newcommand{\ABGABEDATUM}{bis zum 16. Januar 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\eps}{\varepsilon}
\newcommand{\E}{\mathbf{E}}
\DeclareMathOperator{\NN}{NN}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\VD}{VD}
\renewcommand{\Pr}{\mathbf{Pr}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Randomisierte Algorithmen}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Paul Seiferth, Max Willert

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm
\noindent


\begin{description}
\AUFGABE{Voronoi Diagramme}{15 Punkte}

Sei $P \subset \R^2$ endlich mit
(i) $|P| \geq 3$; (ii) keine vier Punkte von $P$ liegen 
auf einem gemeinsamen Kreis; und (iii) die Punkte von $P$
liegen nicht alle auf einer Geraden. 
F\"ur $x \in \R^2$, setze 
$\NN(x) = \{ p \in P \mid d(x,p) = \min_{q \in P} d(x,q)\}$.
Wir definieren $\VD(P) = \{ x \in \R^2 \mid |\NN(x)| \geq 2\}$.

Den Elemente von $V(P) = \{ v \in \R^2 \mid |\NN(v)| \geq 3\}$
hei\ss{}en \emph{Voronoi-Knoten}. Die Komponenten von
$\VD(P) \setminus V(P)$ hei\ss{}en \emph{Voronoi-Kanten}.
Die Komponenten von $\R^2 \setminus \VD(P)$ hei\ss{}en
\emph{Voronoi-Zellen}. 

Zeigen Sie:

\begin{enumerate}
  \item Ein Punkt $v \in \R^2$ ist Voronoi-Knoten genau dann, 
        wenn es eine geschlossene Kreisscheibe $D$ mit Mittelpunkt $v$ 
	gibt, so
        dass $|D \cap P| = 3$ und $\mathring{D} \cap P = \emptyset$ ist.
        Jeder Voronoi-Knoten ist inzident zu genau drei Voronoi-Kanten.
  \item Seien $p, q \in P$. Der \emph{Bisektor} $B_{pq}$ von $p$ und
        $q$ ist die Mittelsenkrechte der Strecke $pq$. 

	Jede Voronoi-Kante ist Teilmenge eines Bisektors $B_{pq}$.
        F\"ur jeden Bisektor $B_{pq}$ gibt es h\"ochstens eine 
	Voronoi-Kante. 
  \item Alle Voronoi-Zellen sind konvex.
%  \item Es gibt $O(|P|)$ Voronoi-Knoten und Voronoi-Kanten.
%        Sie d\"urfen verwenden, dass $\VD(P)$ ein 
%	zusammenh\"angender, ebener Graph mit $|P|$ Facetten ist.
\end{enumerate}

\AUFGABE{Kleine Epsilon-Netze f\"ur Halbebenen}{15 Punkte}

Betrachten Sie den Range Space der \emph{geschlossenen Halbebenen},
d.h., den Range Space
$(\R^2, \mathcal{R})$ mit
\begin{multline*}
\mathcal{R} = \{ \{(x,y) \mid y \leq ax + b \} \mid a,b \in \R\}
\cup\\
\{ \{(x,y) \mid y \geq ax + b \} \mid a,b \in \R\} \cup
\{ \{(x,y) \mid x \leq  a\} \mid a \in \R\} .
\end{multline*}

Sei $P \subset \R^2$, so dass
keine drei Punkte in $P$ auf einer Geraden liegen. Sei
$N_1 \subset P$ eine Teilmenge von $P$. 
Die \emph{konvexe H\"ulle} von $N_1$, $\conv(N_1)$, ist
die kleinste konvexe Menge, die $N_1$ enth\"alt.
Wir wissen, dass $\conv(N_1)$ ein konvexes Polygon ist, dessen
Ecken Punkte aus $N_1$ sind. 
Seien $p,q \in N_1$ und $\ell_{pq}$ die Gerade durch $p$ und $q$.
Dann ist $e = pq$ genau dann eine Kante von $\conv(N_1)$, wenn
eine der beiden durch $\ell_{pq}$ begrenzten offenen Halbebenen
keine Punkte aus  $P$ enth\"alt. Wir bezeichnen diese offene Halbebene
als $h_e^-$, und schreiben $P_e = P \cap h_e^-$.

Benutzen Sie diese Definitionen und Fakten, um zu beweisen,
dass der Range Space der geschlossenen Halbebenen lineare
$\eps$-Netze besitzt. 
Das hei\ss{}t, f\"ur alle
$r \in \{1, \dots, |P|\}$ existiert eine Teilmenge $N \subset P$, 
$|N| = O(r)$, so dass f\"ur alle $R \in \mathcal{R}$ mit
$|P \cap R| \geq n/r$ gilt: $P \cap N \neq \emptyset$.

Gehen Sie dabei analog zum Beweis f\"ur
Kreisscheiben aus der Vorlesung vor.

\emph{Hinweis}: Bei Ihrer Analyse sollen Sie folgende
Variante der Chazelle-Friedman Schranke verwenden.
Sei $P \subseteq \R^2$ mit $|P| = n$, und sei
$p \in (0,1]$ gro\ss{} genug und $p' = p/2$.
Sei $R \subseteq P$ eine zuf\"allige Teilmenge
mit $|R| = pn$ und $R' \subseteq P$ eine zuf\"allige
Teilmenge mit $|R'| = p'n$. Sei $(u,v) \in P^2$ und sei
$e_{uv}$ die \emph{gerichtete} Kante von $u$ nach $v$.
Sei $h_{uv}$ die offene Halbebene links von $e_{uv}$. Seien
$B_{uv} = P \cap h_{uv}$ und $b_{uv} = |B_{uv}|$. Dann existert eine
Kontante $C$, so dass gilt
\[
  \Pr[e_{uv} \in \text{conv}(R)] \leq C e^{-\frac{pb_{uv}}{2}} \Pr [e_{uv} \in \text{conv}(R')].
\]
Dabei bedeutet $e \in \text{conv}(R)$, dass die gerichtete Kante $e$ \emph{im Uhrzeigersinn}
auf der konvexen H\"ulle von $R$ vorkommt. Beweisen Sie diese Variante der Chazelle-Friedman
Schranke und verwenden Sie sie in Ihrer Analyse.
\end{description}
\end{document}
