\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts,graphicx}

\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'10)} \\[1ex]
{Prof.~Erik Demaine \qquad Dr.\ Andr\'e Schulz \qquad TA: Aleksandar Zlateski} \\[2ex]
\framebox{Problem 2} \quad {\em Due: Thursday, Feb.\ 18}
\end{center}

Be sure to read the instructions on the assignments section of the
class web page.

\paragraph{\boldmath Query time kd-trees.}
We consider a kd-tree that stores $n$ points in the plane.
Every node $v$ of the kd-tree represents a region $\tt{region}(v)$ in the induced subdivision of the plane.
\begin{enumerate}
\item Show that the boundary of an  (axis-parallel) query rectangle can intersect at most $O(\sqrt{n})$ such regions.
\item Show that $\Omega(\sqrt{n})$ is a lower bound for the maximal number of regions that intersect the boundary of an axis-parallel query rectangle by defining a set of $n$ points and a query rectangle appropriately.
\end{enumerate}

%\paragraph{\boldmath Interval queries.}
%Let $I$ be a collection of $n$ closed intervals on the real line. We want to report all intervals of $I$ that contain a query interval $[a,b]$. Design a data structure that can answer such queries in $O(\log n +k )$ time and uses $O(n)$ space. \emph{Hint:} Use a priority search tree.


\paragraph{\boldmath Segment stabbing.}

Let $S$ be a set of disjoint line segments in the plane. 
\begin{enumerate}
\item Develop a data structure that can report all $s\in S$ that are hit by a vertical ray emanating from $(x,y)$ towards $\infty$, that is
\[\tt{Above}(x,y):=\{s\in S \; | \: s\cap \{(x,y')\: |\:y\leq y'\}\not = \emptyset \}.\]
Query times should be $O(\log n +k)$.
\item Develop a data structure that can report all $s\in S$ that are hit by a line segment with endpoints $(x,y_1)$  and $(x,y_2)$, that is
\[\tt{Between}(x,y_1,y_2):=\{s\in S \; | \: s\cap \{(x,y')\: |\: y_1\leq y'\leq y_2\}\not = \emptyset \}\]
Query times should be $O(\log^2 n +k)$.
\end{enumerate}
\emph{Hint:} Modify a segment tree. 
\begin{figure}[h]
\begin{center}
\begin{tabular}{cp{1cm}c}
\includegraphics[width=.3\textwidth]{above}&&
\includegraphics[width=.3\textwidth]{between}\\
$\tt{Above}(x,y)$ & &$\tt{Between}(x,y_1,y_2)$
\end{tabular}
\end{center}
\caption{Illustration what the queries should report (thick lines).}
\end{figure}
\end{document}
