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

\newcommand{\ZETTELNUMMER}{7}

\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}}
\newcommand{\eps}{\varepsilon}

\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]
7th 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{Reduction to the Near-Neighbor Problem} 

Fill in the missing details in the reduction from the
nearest-neighbor to the near-neighbor problem.
In particular, give the details of the approximate clustering
algorithm, analyze the space requirement, and show that the
choice of parameters give the desired approximation.

\AUFGABE{A Simple Near-Neighbor Structure}

Let $\eps \in (0, 1/2)$ and set $c = 1 + \eps$. Show how to solve the $c$-approximate
$r$-near neighbor problem in $d$ dimensions with 
$n \cdot O(1/\eps)^d$ preprocessing
and space, and query time $O(d)$. You may use hashing and the floor
function. How do you feel about this result?

\emph{Hint}: Use a grid of appropriate size. It may be useful to know
that the volume of the $d$-dimensional ball with radius $a$ is
\[
  \frac{\pi^{d/2}}{(d/2)!} \cdot a^d,
\]
for $d$ even and
\[
  \frac{2(2\pi)^{(d-1)/2}}{d!!} \cdot a^d,
\]
for $d$ odd. Here, $d!!$ is the \emph{double factorial}, defined as 
$d!! = \prod_{i=0}^{(d-1)/2} (2i + 1)$, the product of all odd integers
from $1$ to $d$.

\AUFGABE{The Number of Resolutions}

Let $P \subseteq \R^d$ with $|P|=n$. Set 
\[
U = \{ i \in \mathbb{Z} \mid \text{there are } p,q \in P \text{ with }
  2^i \leq d(p,q) < 2^{i+1} \}.
\]

Show that $|U| = O(n)$. 

\emph{Hint}: One approach might be to consider a compressed quadtree for $P$ 
and to charge the resolutions to the nodes of the quadtree.
\end{description}
\end{document}
