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

\newcommand{\ZETTELNUMMER}{2}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[1]{\vspace{0.3cm}\item[Problem \arabic{AUFGNR}]\stepcounter{AUFGNR} #1}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}

\DeclareMathOperator{\CH}{\text{CH}}
\DeclareMathOperator{\R}{\mathbb{R}}

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

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
2nd Problem Set for the MDS Block Course on

\smallskip
\noindent
\large
\textbf{High-Dimensional Computational Geometry} \\[0.5ex]
\normalsize
Helmut Alt, Wolfgang Mulzer\hfill Summer 2013

\medskip\hrule

\smallskip
\noindent
The problems will be discussed in the afternoon session.\\


%\vskip 0.5cm

\begin{description}
\AUFGABE{Seidel's Algorithm --- Details} 

Work out the implementation details of Seidel's convex hull
algorithm. Which data structures are needed? How are they organized?
How is the conflict location implemented? How is the convex hull
updated in each step?

\AUFGABE{Moments of the Binomial Distribution}

For $p \in [0,1]$ and $n \in \mathbb{N}$,
let $B(n,p)$ denote the binomial distribution with $n$ trials
and success probability $p$. Let $X$ be distributed according to
$B(n,p)$ and let $c \in \mathbb{N}_0$. Show
that $\text{E}[X^c] \leq (c+np)^c$. 
For this, prove the stronger bound 
$\text{E}[(X+ j)^c] \leq (c+np+ j)^c$, for all $j \in \mathbb{N}_0$
by induction on $c$.


\begin{enumerate}
  \item Check that the claim holds for $c = 0$ and $c=1$.
  \item Show that for $c \geq 1$, we have
  \[ 
    \text{E}[(X+ j)^{c+1}] = j\text{E}[(X+ j)^{c}]
      + \sum_{i=1}^{n} p\, \text{E}[(X+ j)^{c} \mid X_i = 1].
  \]
    Here, we put $X = \sum_{i=1}^n X_i$, 
    where $X_i$ is an indicator random variable that
    is $1$ with probability $p$.
  \item Use (b) to finish the induction on $c$.
\end{enumerate}

\emph{Remark}: This bound is due to Br\"onnimann, Chazelle, and 
Matou\v{s}ek.

\AUFGABE{Chazelle-Friedman Bound}

Let $H$ be a set of $n$ hyperplanes in $\R^d$ whose intersection is
non-empty and bounded. Let $p \in [0,1]$ and let $S \subseteq H$ be a 
subset that contains each hyperplane in $H$ independently with probability $p$.
Let $t \in \mathbb{N}$, and let $S_{\geq t}$ be the number of simplices 
$\sigma$ in the canonical triangulation of $S^\cap$ with 
conflict size $n_\sigma \geq t/p$.
Then, the Chazelle-Friedman bound states that 
\[
\text{E}[S_{\geq t}] = O\bigl(t^{d^2}2^{-t} (pn)^{\lfloor d/2 \rfloor}\bigr).
\]

\begin{enumerate}
  \item Let $T$ be sample that contains each hyperplane
    with probability $p/t$. Argue that the expected number of
    simplices in the canonical triangulation of $T$ is
    $O\bigl((pn/t)^{\lfloor d/2 \rfloor}\bigr)$.
  \item Let $\sigma$ by a possible simplex with $n_\sigma \geq t/p$. Denote by
    $p_S(\sigma)$ the probability that $\sigma$ occurs in 
    the canonical triangulation  of $S^{\cap}$ and by $p_T$ the probability that 
    $\sigma$ occurs in the canonical triangulation of $T^{\cap}$. Show that
    \[
        \frac{p_T(\sigma)}{p_S(\sigma)} \geq t^{-d^2} e^{t-2}.
    \]

    \emph{Hint}: Use the bounds $1-x \leq e^{-x}$ for all $x$ and
      $1-x \geq e^{-2x}$ for $0 \leq x \leq 1/2$.
  \item Using (b), show that
    \[
    \text{E}[S_{\geq t}] \leq t^{d^2} e^{2-t} \, \text{E}[|T^{\cap}|],
    \]
    where $|T^{\cap}|$ is the number of simplices in the canonical triangulation of
    $T^\cap$.
  \item Conclude the Chazelle-Friedman bound.
\end{enumerate}
\end{description}
\end{document}
