\documentclass{article}
\input{6046preamble}


\begin{document}
\pset{7-2}{Dan Ports}{No collab}{Recitation \#8}

\begin{ppart}{Algorithm}
We will use essentially the same sweep-line approach for solving the problem as the output-sensitive algorithm in the lecture: we will sweep through the plane from left to right, keeping track of which horizontal segments currently intersect the sweep line, and whenever we hit a vertical segment we will count the number of horizontal segments it intersects. However, to maintain this information, we will make use of an order-statistic tree (CLRS chapter 14), sorted by y-coordinate. This data structure allows us to insert an element, remove an element, find an element by value, or find the rank of an element, each in $O(\lg n)$ time.
\paragraph{}
As we sweep from left to right, we need to consider $\Theta(n)$ ``points of interest'', defined as the left and right x-coordinates of each horizontal segment and the x-coordinate of each vertical segment. Using a sorting algorithm, we can place these in increasing order by x-coordinate in $O(n \lg n)$ time, along with pointers so we can find the other endpoints of the segment. We initialize a counter for the total number of intersection points to be zero. Then we consider each point of interest in increasing order by x-coordinate. If that point is the left endpoint of a horizontal segment, we find the y-coordinate and add it to our order-statistic tree, in $O(\lg n)$ time. If it is the right endpoint of a horizontal segment, we find the segment's y-coordinate and remove it from the order-statistic tree. If it is a vertical segment, we need to find the number of points which intersect it. To do this, we find the y-coordinates of the vertical segment --- call them $y_1$ and $y_2$, and assume without loss of generality that $y_1 < y_2$. We find the element in the tree which has the smallest y-value greater than or equal to $y_1$ (call it $v_1$) and the element which has the largest y-value less than or equal to $y_2$ (call it $v_2)$. Then the number of segments intersected by the vertical segment is $\textsc{Rank}(v_2) - \textsc{Rank}(v_1) + 1$. We increment the counter by this amount. Once we have reached the last point of interest, we return the value in the counter.
\end{ppart}

\begin{ppart}{Runtime analysis}
We can do all the preprocessing and sorting of the input points in $O(n \lg n)$ time, generating a list of points of interest in increasing order. There are $2$ points of interest per horizontal segment and $1$ per vertical segment, so $\Theta(n)$ total points of interest. For each point of interest, we require $O(\lg n)$ time: to add or remove an entry from the order-statistic tree if it is an endpoint of a horizontal segment, or to locate $v_1$ and $v_2$ and calculate their rank if it is a vertical segment. Thus the overall time requirement of the algorithm is $O(n \lg n)$.
\end{ppart}

\begin{ppart}{Proof of correctness}
We assume the correctness of the algorithm presented in the lecture. Since the bulk of this algorithm is essentially the same as that algorithm, we need only prove that maintaining the order-statistic tree gives the correct results. We use the invariant that the order-statistic tree contains the y-coordinate of each horizontal segment that the sweep line intersects. The procedures we follow when advancing the sweep line to the left or right endpoints of a horizontal line clearly maintain this invariant. Thus, when the sweep line is advanced to a vertical segment, it will intersect every horizontal line whose y-coordinate is between the endpoints of the vertical line. The number of such intersections is $\textsc{Rank}(v_2) - \textsc{Rank}(v_1) + 1$ for $v_1$ and $v_2$ as defined above (we add 1 because we want to include the points $v_1$ and $v_2$ in the count). The justification from this statement follows from the correctness of CLRS's order-statistic tree algorithm, which we assume.
\end{ppart}
\end{document}