\input ncs445hdr
% this is nh2cs445.tex of January 12, 1983 10:35 PM
\def\rtitle{Homework 2}
\def\header{Homework 2}
\setcount1 6
\sect{Second Problem Set, due Thursday, January 20}
{\caveat In the problems below, wherever appropriate, interpret ‘‘polygon’’ to mean ‘‘polygonal tracing’’, and ‘‘convex polygon’’ to mean ‘‘convex polygonal tracing’’.}\par
\prob Let $\Sscr$ be an $n$-sided simple polygon and $p$ a point in the plane. We discussed two definitions of the winding number of a point with respect to an oriented closed curve. One was based on the total number of times the curve winds around the point, and the other was based on counting signed crossings of the curve with some ray out of $p$.\par
(a) Use these definitions to develop two algorithms for testing if $p$ is inside $\Sscr$. Assume the standard representation for $\Sscr$, namely an array containing its vertices in counterclockwise order. Be sure to discuss how to handle, or avoid, degenerate cases. What is the complexity of your algorithms (as a function of $n$)? Which one would you use in practice?\par
(b) Show that in a single walk around $\Sscr$ we can find the point on $\Sscr$ closest to $p$. Such a point is either a vertex of $\Sscr$, or is interior to an edge of $\Sscr$. Prove that once the vertex, or edge, of $\Sscr$ containing this nearest neighbor is known, then we can decide whether $p$ is inside $\Sscr$ in constant further time.\par
\prob We showed that two non-intersecting convex polygons $\Pscr$ and $\Qscr$ have two inner common tangents. From the convolution theorem we also know that whenever $\Pscr$ and $\Qscr$ don’t intersect, the origin $O$ is outside the convolution $\Rscr = \Pscr\ast\Qscr↑{-I}$. How are the two tangents from $O$ to $\Rscr$ related to the inner common tangents of $\Pscr$ and $\Qscr$?\par
{\caveat Given a convex polygon $\PScr$ and a point $q$ outside it, there are two tangents from $q$ to $\Pscr$. These tangents subdivide the edges of $\Pscr$ into two chains. We will call them the near chain and far chain respectively, in the obvious manner.}\par
\prob Let $\Pscr$ be a convex polygon, $p$ a point on its boundary, and $\lscr$ a line in the plane. Consider the distance from $p$ to $\lscr$. How many local maxima and minima can this function have as $p$ makes a complete tour counterclockwise around $\Pscr$? Be sure to consider both the case where $\lscr$ intersects $\Pscr$ and where it doesn’t. Answer the same question for the distance of $p$ to another fixed point $q$. Again consider both cases where $q$ is inside and outside $\Pscr$. In the latter case does anything special hold for the portion of the tour corresponding to the near chain? \par
\prob Let $\Pscr$ be a convex polygon and $q$ a point outside of it. We developed algorithms for computing the tangents from $q$ to $\Pscr$. Prove that the closest point $p$ of $\Pscr$ to $q$ lies in the near chain. Use the results of the previous problem to devise an algorithm for finding the closest point $p$ on $\Pscr$ to $q$ that works in time $O(\lg n)$, where $n$ is the number of vertices (and edges) of $\Pscr$.\par
{\caveat The following two are extra credit problems.}\par
\prob Suppose you are implementing the polygon inclusion test described in problem 6(a) as being based on the ‘‘winding’’ of $\Sscr$ around $p$. Suppose further that all vertices of $\Sscr$ and $p$ are points on the integer lattice. To what precision must you do your computations to be able to trust your answer despite round-off errors in the arithmetic?\par
\prob Is the following problem $\Nscr\Pscr$-complete? Given a convex polygon $\Pscr$, can it be written as the convolution $\Pscr = \Qscr\ast\Rscr$ of two other convex polygons $\Qscr$ and $\Rscr$, each of which has strictly fewer sides than $\Rscr$? (A possible objection to this question has to do with the need to specify infinite precision real quantities to a machine. See the discussion on the traveling salesman problem in Garey and Johnson in regards to this issue.)\par
\vfill\eject\end