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

\newcommand{\ZETTELNUMMER}{3}

\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]
3rd Problem Set for the MDS Block Course on

\medskip
\noindent
\large
\textbf{High-Dimensional Computational Geometry} 

\medskip
\noindent
\normalsize
Helmut Alt, Wolfgang Mulzer\hfill Summer 2013

\medskip\hrule

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


%\vskip 0.5cm

\begin{description}
\AUFGABE{Exact Nearest-Neighbor Search in $d$ Dimensions} 

Let $P$ be a set of points in $\R^d$. We want to
obtain a data structure with space $O(n^{\lceil d/2 \rceil + \eps})$
that can answer the following query in $O(\log n)$ time:
given a point $q \in \R^d$, find the point $p \in P$ that is closest to $q$.

Let $H$ be the hyperplanes
obtained by lifting $P$ to the $(d+1)$-dimensional unit paraboloid and taking tangents. 
As we saw in
class, to answer a nearest neighbor query, we need to find the intersection of 
the vertical ray through $q$ in $\R^{d+1}$ with the upper envelope of 
$H$.
Fix some constant $t \in \mathbb{N}$.

\begin{enumerate}
  \item Let $S \subseteq H$ be obtained by taking each hyperplane with probability
    $t/n$. Let $\mathcal{T}$ be the canonical triangulation of the intersection of the
    halfspaces above the hyperplanes in $S$. Show that with probability at least $1/2$,
    the triangulation $\mathcal{T}$ has $O(t^{\lceil d /2 \rceil})$ simplices and each
    simplex in $\mathcal{T}$ is intersected by $O((n/t) \log t)$ hyperplanes from $H$.

  \emph{Hint}: Use the Chazelle-Friedman bound.

 \item Use (a) recursively to obtain a data structure that can answer nearest neighbor
    queries in time $O(t^{\lceil d/2 \rceil} \log n)$ and
     whose space requirement fulfills the recursion
    \[
      S(n) = O(t^{\lceil d/2 \rceil}) +   O(t^{\lceil d/2 \rceil})\, S(O((n/t) \log t)).
    \]

  \item Show that the recursion from (b) solves to 
     $O(n^{\lceil d/2 \rceil + \eps})$, where $\eps > 0$ is some constant that gets smaller
     as $t$ gets larger.
\end{enumerate}

\AUFGABE{\#P}
\begin{enumerate}
\item 
Let $FP$ be the set of functions from $\{0,1\}^*$ to $\mathbb{N}$ that are computable in polynomial time. Show that $FP \subseteq \#P$.

\item 
Is the standard reduction from SAT to 3SAT parsimonious? Why is \#3SAT \#P-complete provided that \#SAT is \#P-complete, nevertheless?
\end{enumerate}

\newpage
\AUFGABE{number of linear extensions}

Show that the following partial order has $\frac{((a+1)b+c)!}{(a+1)^b}$ linear extensions. \\ {\em Hint}: probabilistic argument.

%
\begin{center} 
\includegraphics[width=8cm]{partord.pdf}
\end{center}
%

\end{description}
\end{document}
