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

\usepackage{epsfig}%
\usepackage{graphics}%
\usepackage{enumerate}


\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'07)} \\[1ex]
{Prof.~Erik Demaine \quad\quad TA: Oren Weimann} \\[2ex]
\framebox{Problem 8} \quad {\em Due: Wednesday, Apr. 18}
\end{center}

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

\paragraph{\boldmath Range Queries in 2D.}

Consider a static set $S$ of points in the plane whose coordinates
are integers from $\{1,\ldots,n\}$. The general \emph{existential 2D
query} is given a rectangle $[a, b] \times [c, d]$ and asks if $S
\cap ([a, b] \times [c, d]) \neq \emptyset$.

A \emph{three sided query} is an existential 2D query where $a=0$. A
\emph{dominance query} is an existential 2D query where $a=c=0$.
Suggest a data structure that can answer three sided queries in
$O(1)$ time. What is the preprocessing time?

\paragraph{\boldmath From Segment Stabbing to Existential dominance Queries in 2D.}

Consider the following segment stabbing problem. We are given a set
of closed segments on the line, $S = \{[a_i, b_i] $ $|$ $ i = 1
\ldots n\}$. A query is of the form: given $x$, does $x$ stab any
segment? That is, $\exists [a, b] \in S : x \in [a, b]$?

Prove that segment stabbing reduces to existential dominance queries
in 2D (if you can solve the latter, you can also solve the former in
the same time and space bounds). Assume coordinates are integers in
$\{0,\ldots, u\}$.

\paragraph{\boldmath From Colored Predecessor to Segment Stabbing}

The colored predecessor problem considers a set of points colored
red or blue, and asks for the color of the predecessor of some $x$.

Prove that the static colored predecessor problem reduces to static
segment stabbing.

\vspace{1cm}

This shows that the lower bounds for predecessor also apply to
existential range queries. Note that we are reducing to the least
general type of range queries (dominance), so the lower bound is as
strong as possible.



\end{document}