\input cs445hdr
% this is hmwk6cs445.tex of March 1, 1982 3:05 PM

\def\title{Homework 6}
\def\header{Homework 6}
\setcount1 26

\sect{Sixth Problem Set, due Tuesday, March 9}

\prob We are interested in the set of directions with respect to which a simple polygon is monotone. As usual, we prefer to think of directions as pairs of antipodal points on the direction circle. Label such a pair $M$ if our polygon is monotone in that direction, and $N$ otherwise. Is there any constraint on the pattern of $M$’s and $N$’s that can arise out of a given simple polygon? Can you characterize all legal patterns?\par

\prob When discussing Dan Greene’s algorithm in class for the optimum subdivision of a simple polygon into convex pieces, we made use of a preprocessing step where we computed all ``visible’’ pairs of vertices $(vǐ,vǰ)$, that is all pairs where $vǐvǰ$ is an interior diagonal. Give an efficient algorithm for finding all visible pairs of vertices of a simple polygon. How fast does your algorithm run?\par

\prob In previous problems we showed how to find the nearest neighbor vertex of each vertex of a simple polygon in linear time. Show that the Voronoi diagram can be used to find the nearest neighbor of each of $n$ arbitrary points in the plane in time $O(n\lg n)$.\par

\prob Given a set of $n$ points in the plane, show how the Voronoi diagram can be used to find the largest circle containing no points of the set (in its interior) and yet whose center is on or in the convex hull of our points.\par

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

\prob Show how to account for the diagonals drawn in Dan Greene’s algorithm for decomposing a monotone polygon into convex pieces, so as to prove that his method always produces a decomposition whose number of pieces is no more than four times the minimum possible.\par

\vfill\eject\end