\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 3} \quad {\em Due: Thursday, Feb.\ 25}
\end{center}

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

\paragraph{\boldmath Ray Shooting in Simple Polygons.}

\begin{enumerate}
\item Let $w_1,w_2,\dotsc ,w_k$ be positive weights we want to store in a weight balanced binary search tree (WBBST). We denote $\sum_{j\leq k} w_j$ by $W$. To built the WBBST we find the unique element $w_r$ such that the sums $\sum_{j< r} w_j$ and $\sum_{j> r} w_j$ are both at most $W/2$. We make the element $w_r$ the root of the WBBST and recurse on the two remaining subsets (left and right of $w_r$).
\begin{enumerate}
\item[(a)] Show that we can search for an item with weight $w_i$ in the WBBST in $O(1+\log(W/w_i))$ time.
\item[(b)] To search through all home-in situations that occur during the ray shooting algorithm we use a WBBST for every concave chain of the balanced pseudo-triangulation. For an edge  we choose as weight its \emph{bay-size} (= number of edges of the opposing polygon). Show that we can answer the searches for all home-in situations  using  $O(\log n)$ time in total.
\end{enumerate}
\item By adding  additional interior points we can transform a balanced pseudo-triangulation into a pseudo-triangulation where every pseudo-triangle has only one concave chain. Since we add at most 6 new pseudo-triangles any line intersects at most  $O(\log n)$ of these special pseudo-triangles.\\
Show how to triangulate the special pseudo-triangles using additional points, such that any line intersects at most $O(\log^2 n)$ triangles.   
\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{2cm}c}
\includegraphics[width=.25\textwidth]{baysize}&&
\includegraphics[width=.25\textwidth]{boomerang}\\
(i) & & (ii)
\end{tabular}
\end{center}
\caption{The bay-sizes of the red chain of $\Delta$ in (i) are from left to rigth: 7,3,1,6. Picture (ii) shows how to decompose a pseudo-triangle into pseudo-triangles with at most one concave chain using additional points.}
\end{figure}
\end{document}
