\input cs445hdr
% this is hmwk5cs445.tex of February 22, 1982 2:15 PM

\def\title{Homework 5}
\def\header{Homework 5}
\setcount1 21

\sect{Fifth Problem Set, due Tuesday, March 2}

\prob Give an algorithm for determining whether any two of $n$ convex $k$-gons in the plane intersect, in time $O(nk+n\lg n\lg k)$ and space $O(nk)$.\par

\prob Suppose we have a dynamic set of semi-infinite line segments beginning at points $(x,y)$ of the plane and extending upwards in $y$. From a given point $(x↑\prime,y↑\prime)$, which of these line segments would be visible along a line of increasing $x$? Show that McCreight’s priority search trees can be used to solve this problem in both the situation where we think of the line segments as being opaque, and where we think of the line segments as being transparent. Your time bounds should be of the form $O(\lg n + s)$, where $n$ is the number of segments present, and $s$ is the number of segments reported. Can you still maintain logarithmic (or nearly so) bounds if the given segments are allowed to be finite instead?\par

\prob A {\it rectagon} is a simple polygon whose sides are constrained to be parallel to the $x$ or $y$ axes. Given a rectagon specified as a sequence of vertices, compute the largest square aligned with the axes that fits entirely within the rectagon. How fast is your algorithm?\par

\prob We saw in class that the regularization algorithm for breaking up a simple polygon into monotone pieces works in two passes. In the first pass the vertices are traversed in order of decreasing $y$ coordinate, and in the second in order of increasing $y$. Given the monotone pieces, still another pass over the vertices in order of decreasing $y$ computes the triangulation. Show that in fact this entire computation can be done, and therefore the triangulation can be output, in a {\it single} pass over the vertices in decreasing $y$ order. (The overall cost of the algorithm should remain $O(n\lg n)$.)\par

{\caveat The following is an extra credit problem.}

\prob Extend the algorithm of the previous problem to give a triangulation even in the case where the original polygon is not simple. Triangles may now use as vertices the intersection points of the original edges. The cost of your algorithm ought to be $O((n+i)\lg n)$, where $i$ is the number of edge intersections.\par

\vfill\eject\end