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

\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'12)} \\[1ex]
{Prof.~Erik Demaine \qquad TAs: Tom Morgan, Justin Zhang} \\[2ex]
\framebox{Problem 5} \quad {\em Due: Thursday, Mar.\ 22}
\end{center}

Be sure to read the instructions on the assignments section of the
class web page.  Remember to keep your solutions to one page!

\paragraph{Orthogonal line segment intersection.}

Given a set of $N$ horizontal and vertical line segments, develop and analyze a cache-oblivious algorithm to find the number of vertical segments intersecting each horizontal segment in $O(\frac{N}{B} \log_{M/B} \frac{N}{B})$ memory transfers.  You may assume that the endpoints of any two different line segments do not have the same $x$ or $y$ value.

\paragraph{Line segment visibility from a point.}

Given a set of $N$ line segments and a point $p$, we would like to find the clockwise list of partial line segments visible from $p$.  A (partial) line segment is visible from $p$ if, for any point along the segment, a line can be drawn from that point to $p$ without intersecting any other line segment.  If a line segment is only partially visible from $p$, then only the segment that is visible should appear in the output list.  A single line segment may contain many partial segments in the output list.  Develop and analyze a cache-oblivious algorithm to accomplish this in $O(\frac{N}{B} \log_{M/B} \frac{N}{B} + \frac{K}{B})$ memory transfers, where $K$ is the size of the output.  You may assume that no two points in the input lie along the same line to $p$, and that no two line segments intersect.

\end{document}
