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

\begin{document}
\psetnum{9}
\date{2005/04/15}

\begin{pset}
  
\paragraph{Part 1}
Suppose we are given an instance of the static colored predecessor
problem, i.e. a set of points colored red and blue. We reduce this to
the static segment stabbing problem. We begin by sorting the points;
call the sorted order $p_i, p_2, \ldots, p_n$. For each red $p_i$, we
create a segment $[p_i, p_{i+1}]$. We also separately keep track of
the values and colors of the  smallest and largest points $p_1$ and
$p_n$, and use these to answer queries for $x < p_1$ and $x > p_n$ in
the obvious way. For all other queries $x$, we check whether $x$ stabs
one of the segments, and return red if so and blue if not.

\paragraph{Part 2}
Now suppose we are given an instance of the static segment stabbing
problem: a set of segment $[a_i, b_i]$ on the line, where the values
of the points are bounded by $u$. We reduce segment stabbing queries
to two-dimensional existential dominance queries. For each segment
$[a_i, b_i]$, we create a point $\tup<a_i, u - b_i>$. Then, to perform
a segment-stabbing query for a value $x$, we perform a dominance query
for the rectangle with one corner at $\tup<0,0>$ and the other at
$\tup<x, u-x>$. This checks whether there is a segment such that $a_i
\le x$ and $b_i \ge x$ (so that $u - b_i \le u - x_i$), which is
precisely the definition of whether $x$ stabs a segment.

\paragraph{Part 3}
We now reduce dynamic marked ancestor to dynamic segment stabbing. In
preprocessing, when we are given the static tree, we compute the Euler
tour of the tree and create a table mapping each node of the tree to
its corresponding indices in the Euler tour (of which there are at
most three). We use these indices to define the line on which we place
segments in the segment stabbing problem. When a node is marked,
we find its first and last appearances in the Euler tour, and mark the
segment corresponding to the region between these indices; when a node
is unmarked, we remove the corresponding segment.

Now, when a query arrives for some node $x$, we look up in the table
one of its indices in the Euler tour, and check whether that point
stabs a marked segment, and if so return true. To see that this is the
correct result, note that the point stabs some segment if and only if
one of $x$'s indices in the Euler tour is between two of the indices
of some marked node, which means that it is in the marked node's
subtree.  This is the definition of the marked ancestor problem. The
reduction can be done with linear time for preprocessing to compute
the Euler tour, and constant time per query to map to a segment
stabbing query using the lookup table.
\end{pset}
\end{document}