\documentclass{article}
\input{6897-preamble}

\begin{document}
\psetnum{8}
\date{2005/04/08}

\begin{pset}
\paragraph{Three-sided queries}
Suppose we wish to answer three-sided queries of the form $[a=0,b]
\times [c,d]$. We construct a RMQ data structure, where the value of
each point is its first coordinate, and the points are ordered by
their second coordinates. Then to perform a 3-sided query, we can
simply search for the minimum value between indexes $b$ and $d$ (since
we are in rank space, this captures the constraint in the second
coordinate). If the minimum value is less than $c$, then there exists
a point in the given rectangle; if not, then no such point can exist.

\paragraph{General queries}
We give a method for converting a solution to the three-sided problem
with space bound $n \cdot \sigma$ and query time $\tau$ to a solution to the
general query problem that uses $\bigO{n \lg n \cdot \sigma}$ space and
gives $\bigO{\tau + \lg \lg n}$ query time.

We construct a perfect binary tree over vertical strips of space
(assume \WLOG{} that we are in rank space and $n$ is a power of 2).
The first node represents the entire space, the second level nodes $[1
\ldots \nicefrac n2]$ and $[\nicefrac n2 + 1, n]$, etc.
until the final $n$ nodes representing each possible $y$ value. At
each node we build two three-sided structures of the points in the
associated strip, one with the left coordinate fixed at the left side
of the strip, and one with the right coordinate fixed at the right side. Note
that the height of the tree is $\lg n$, and each point appears in $2 \lg
n$ three-sided structures, so the total space required is $\bigO{n \lg
  n \cdot \sigma}$.

%% To perform a query, we begin at the root and perform a three-sided
%% query, ignoring the $a$ coordinate. Certainly this query is a
%% relaxation of the general query, so if the response is negative, the
%% same is true for the general query, and we can stop. Otherwise, we
%% perform the three-sided query on both of the children of the root
%% node:

%% \begin{itemize}
%% \item If the right child represents a strip that begins to the right
%%   of the $a$ coordinate,
%%   \begin{itemize}
%%   \item If the three-sided query returns true on the right child strip,
%%     then we have found a point that is definitely in the query
%%     rectangle, so we are done.
%%   \item If the three-sided query on the right child strip returns
%%     false, then we check the left child (since part of the query
%%     rectangle is in its strip), and recurse on it if the three-sided
%%     query returns true.
%%   \end{itemize}
%% \item If the right child represents a strip that begins to the left of
%%   the $a$ coordinate,
%%   \begin{itemize}
%%   \item If the three-sided query on the right child strip returns
%%     false, then no point in the query rectangle exists, since the
%%     right child strip contains the entire query rectangle. So we
%%     return false.
%%   \item  If the three-sided query on the right child strip returns
%%   true, then we recurse on the right child (since it contains the
%%   entire query rectangle, plus possible other points).
%%   \end{itemize}
%% \end{itemize}

%% We perform the necessary recursions that progressively shrink the size
%% of the strips until we reach the leaves of the tree, at which point no
%% further recursions are possible and the answer to the query is
%% immediate.

%% Since the depth of the tree is $\lg n$, 

To perform a query, we identify the lowest common ancestor of $a$ and
$c$ in the tree --- we can do this in constant time by bitwise XORing
$a$ and $c$ to identify the first bit at which they differ, and using
this to extract their common prefix and index into the tree. This
node's strip contains the full query interval $[a,c]$. Call its left
and right children $x_L$ and $x_R$ respectively. Note that $a$ is
contained in $x_L$'s strip and $c$ in $x_R$'s, since otherwise their
parent would not be the lowest common ancestor.

Call the dividing point between $x_L$ and $x_R$'s strips $p$.
Certainly the query rectangle $\tup<a,b,c,d>$ is exactly the union of
$\tup<a,b,p,d>$ and $\tup<p,b,c,d>$. One of these rectangles is in
$x_L$ and the other in $x_R$, and they both have one side fixed at the
common edge $p$ of the two strips. So we simply perform a
fixed-left-side query $\tup<a,b,\infty,d>$ in $x_L$ and a
fixed-right-side query $\tup<0,b,c,d>$ in $x_R$; if either one returns
true, then a point exists in the query rectangle; otherwise, no such
point exists.

Performing the lookup requires two three-sided queries to be
performed, plus the predecessor queries to convert to the appropriate
rank space for each one, for a time bound of $\bigO{\tau + \lg \lg
  n}$. 
\end{pset}
\end{document}