\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\usepackage{epsfig}%
\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 -- Solution}
\end{center}
\paragraph{\boldmath Range Queries in 2D.}
For each $y \in \{1, \dots, n\}$, let $A[y] = \min \{ x \mid (x,y)
\in S \}$. When we want to query the range $[0,b] \times [c,d]$, we
use an RMQ query to find $t = \min \{ A[y] \mid y \in [c,d] \}$. If
$t > b$, the range is empty; otherwise, it contains at least one
point.

\paragraph{\boldmath From Segment Stabbing to Existential dominance Queries in 2D.}
Replace a segment $[a,b]$ by the point $(a, u-b)$ in two dimensions.
Now, for some $x$, we query the range $[0,x] \times [0, u-x]$. We
have $(a, u-b) \in [0,x] \times [0, u-x] \iff a \le x, u-b \le u-x
\iff a \le x \le b \iff x \in [a,b]$.

\paragraph{\boldmath From Colored Predecessor to Segment Stabbing}
If we find two consecutive points of the same color, we can
eliminate the second one, and the result of any predecessor query
will not change. Thus, we can assume colors alternate in the sorted
list of points. By symmetry, assume the first point is red. For
every $i$, create a segment between the $2i$-th and $(2i+1)$-st
points (observe that the segments are disjoint). Now, if $x$ stabs a
segment, it's predecessor has an even index, so it is blue.
Otherwise, the predecessor is red.
\end{document}