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

\newcommand{\ZETTELNUMMER}{6}

\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]
6th 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{Approximating $r_\text{med}$} 

Let $P$ be a $d$-dimensional $n$-point set. Define $r_\text{med}$
as the minimum radius such that $\text{CC}_P(r_\text{med})$
contains a component with at least $n/2 + 1$ points.

Consider the following algorithm: Take a random point $p \in P$
and let $r_\text{med}^*$ be the median of the distances
$d(p, q)$ for $q \in P \setminus \{p\}$. Show that with probability at least $1/2$,
we have $r_\text{med} \leq r^*_\text{med} \leq 2(n-1)r_\text{med}$.

\AUFGABE{Voronoi Diagram in $\R^3$}

Show that the three-dimensional Voronoi diagram for $n$ points can have
complexity $\Omega(n^2)$.

\AUFGABE{Exact Nearest Neighbor II}

What is the best query time that you can achieve
for the exact nearest neighbor problem if the 
data structure is allowed space $O(n^{\lceil d/2\rceil})$?

\emph{Hint}:
One possible strategy would be to adapt the randomized convex hull algorithm.

\end{description}
\end{document}
