\input ncs445hdr
% this is nh3cs445.tex of January 18, 1983 11:27 PM

\def\rtitle{Homework 3}
\def\header{Homework 3}
\setcount1 12

\sect{Third Problem Set, due Thursday, January 27}

\prob Consider the extremal points of a convex polygon $P$ in a particular direction, say the $+y$ direction. Show that the set of such points is either a single vertex, or a single edge. Assuming that $P$ is given in the standard representation, find an $O(\lg n)$ algorithm for determining this set of extrema.\par

\prob In problem 8 we saw that the distance of a point touring a convex polygon $P$ to a line $\lscr$ is a bimodal function, if we take distances to be positive on one side of the line and negative on the other. In class we gave an algorithm for determining the tangents from a point to a convex polygon. This algorithm exploited the bimodality of another function and run in time $O(\lg n)$. Show how to do the same for the problem of computing the intersection points (if any) of $P$ and $\lscr$. Some of the details are tricky, so be precise.\par

\prob Show that a tracing $T$ such that $T = T↑{t-I}$ for some vector $t$ has a center of symmetry. What is the position of the center of symmetry in terms of $t$? Show that if two tracings $T$ and $S$ both have centers of symmetry, then so does their convolution $T\ast S$. By convention let us accept a the following type of tracing as a convex tracing, and let us call it a {\it segment} tracing.\par

\vskip 1in

In a sense, a segment tracing is the simplest convex tracing. Note that a segment tracing has a center of symmetry, and therefore so does any convolution $C$ of some number of convex tracings. We know that $C$ must also be a convex tracing. Prove that the converse is also true. Any convex tracing with a center of symmetry factors into the convolution of segment tracings.\par

Finally show that any convex polygon which is the disjoint union of other convex and centrally symmetric convex polygons is itself a centrally symmetric polygon.\par

\prob Given convex polygons $P$ and $Q$ of $p$ and $q$ edges respectively, show how to decide whether $P$ can be translated so as to fit entirely inside $Q$ in time $O(p+q)$.\par

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

\prob We saw that two convex polygons $P$ and $Q$ intersect if and only if the origin lies inside the convolution $C = P\ast Q↑{-I}$. In the algorithm we discussed for testing point inclusion in a convex polygon, a point $x$ is shown to be inside $C$ by exhibiting two sides of $C$ such that a horizontal line through $x$ intersects one side to the left of $x$ and the other to the right. Let us call these two sides the {\it witnesses} to the inclusion of $x$. Simlarly, a witness to the fact that $P$ and $Q$ intersect is a point $z$ belonging to both. Show how, given witnesses testifying that $O\in C$, we can produce a witness for the intersection of $P$ and $Q$. A witness to non-intersection is a separating line. Reformulate and repeat the problem for this case.\par

\vfill\eject\end