\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem} {Theorem}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}


\title{Erwartete Konflikt\"anderung f\"ur die Berechnung der ebenen konvexen 
H\"ulle -- Mulmuleys $\Theta$-Reihe}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle
Sei $P$ eine ebene Punktmenge mit $n$ Punkten. In der Vorlesung
haben wir gesehen, dass die Gesamtkosten f\"ur die Aktualisierung
der Konfliktinformationen w\"ahrend der inkrementellen Konstruktion
von $\conv(P)$ asymptotisch gegeben sind durch
\[
\Theta \eqdef \sum_{(p,q) \in P^2} |P \cap h_{\overrightarrow{pq}}^+|\cdot
[\text{Die Kante }(p,q) \text{ wird im Laufe der inkrementellen Konstruktion 
erzeugt}].
\]
Hierbei bezeichnet $h_{\overrightarrow{pq}}^+$ die offene Halbebene links
von der gerichteten Geraden $\overrightarrow{pq}$, und $[X]$ ist die 
Iverson-Notation: $[X]=1$, falls die Aussage $X$ erf\"ullt ist, und $[X]=0$
sonst.

Die randomisiert inkrementelle Konstruktion von $\conv(P)$ w\"ahlt
zun\"achst eine zuf\"allige Permutation $\sigma$ von $P$ und f\"ugt
dann die Punkte gem\"a\ss{} der von $\sigma$ vorgegebenen Reihenfolge
in die konvexe H\"ulle ein. Wir wollen nun die erwarteten 
Konflikt\"anderungskosten ausrechnen. Aufgrund der Linearit\"at des
Erwartungswerts gilt:
\begin{align*}
\EX_\sigma[\Theta]&=
\sum_{(p,q) \in P^2} |P \cap h_{\overrightarrow{pq}}^+|\cdot
\Pr[\text{Die Kante }(p,q) \text{ wird im Laufe der inkrementellen Konstruktion 
erzeugt}]\\
&=
\sum_{k=1}^{n-3}\sum_{(p,q) \in L_k} k\cdot
\Pr[\text{Die Kante }(p,q) \text{ wird im Laufe der inkrementellen Konstruktion 
erzeugt}],
\end{align*}
wobei $L_k$ die Menge der $k$-Kanten f\"ur $P$ ist (siehe die Definition
im Beweis f\"ur den Satz von Clarkson). Diese Summe hei\ss{}t Mulmuleys 
$\Theta$-Reihe. Da eine $k$-Kante $(p,q)$ genau dann
erzeugt wird, wenn in der zuf\"alligen Permutation die beiden Punkte $p$ und
$q$ vor den $k$ Punkten in $P \cap h_{\overrightarrow{pq}}^+$ erscheinen, gilt
\[
\Pr[\text{Die Kante }(p,q) \text{ wird im Laufe der inkrementellen Konstruktion 
erzeugt}] = \frac{2!k!}{(k+2)!} = \frac{2}{(k+1)(k+2)}.
\]
Folglich
\[
\EX_\sigma[\Theta] = 
\sum_{k=1}^{n-3}\sum_{(p,q) \in L_k} 
\frac{2k}{(k+1)(k+2)} \leq 
\sum_{k=1}^{n-3} \frac{2|L_k|}{k}.
\]
Nun haben wir das Problem, dass wir $|L_k|$ nicht absch\"atzen k\"onnen.
Hier kommen uns nun der Satz von Clarkson und ein h\"ubscher Trick zur Hilfe.
Es gilt n\"amlich $|L_k| = |L_{\leq k}| - |L_{\leq(k-1)}|$, wobei 
$L_{\leq k}$ die Menge aller $\ell$-Kanten von $P$ f\"ur $0 \leq \ell \leq k$ 
bezeichnet. Mit Abelscher partieller Summation folgt nun:
\begin{multline*}
\EX_\sigma[\Theta] \leq 
\sum_{k=1}^{n-3} \frac{2}{k}\Bigl(|L_{\leq k}| - |L_{\leq(k-1)}|\Bigr)\\
= \frac{2}{n-2}|L_{\leq(n-3)}| - 2|L_{\leq0}| +
\sum_{k=1}^{n-3} |L_{\leq k}| \Bigl(\frac{2}{k}-\frac{2}{k+1}\Bigr)
\leq O(n) + \sum_{k=1}^{n-3} \frac{2 |L_{\leq k}|}{k^2},
\end{multline*}
denn $|L_{\leq(n-3)}| = O(n^2)$, $|L_{\leq 0}| = O(n)$ und
\[
\frac{2}{k}-\frac{2}{k+1} = \frac{2}{k(k+1)} \leq \frac{2}{k^2}.
\]
Der Satz von Clarkson besagt, dass $|L_{\leq k}| = O(nk)$, also
\[
\EX_\sigma[\Theta] =
O\Bigl(\sum_{k=1}^{n-3} \frac{nk}{k^2}\Bigr) = 
O\Bigl(n \cdot \sum_{k=1}^{n-3} \frac{1}{k} \Bigr) = O(n \log n).
\]
Der erwartete Aufwand f\"ur die Konflikt\"anderung,
und folglich die erwartete Gesamtlaufzeit f\"ur die randomisiert
inkrementelle Konstruktion der ebenen konvexen H\"ulle, ist $O(n \log n)$.
\end{document}